@vnp has already given an excellent review of your algorithmic problems. I'm not going to duplicate their work. I'm just going to review the code itself.
using namespace std;
Avoid doing the above. It may save you a few keystrokes in a small program like this one, but can turn into a major maintenance headache for a codebase that you need to support. See this question.
long long int n,x,a,b,sum=0,s=1;
- Never declare multiple variables on a single line. It's very easy to screw up the syntax and get some surprising bugs. Declaring each variable on its own line does not make the code slower.
- Don't declare variables until they're needed. You need
n right away, but you don't use a or b until over 50 lines later.
- Give variables descriptive names. In a problem like this, you can get away with using names like
n, a, and b because they're the names in the problem. But what is x? I don't even see it being used at all? Is it vestigial from an earlier attempt at the problem?
On to the next lines....
long long int *size=new long long int[n];
long long int **arr=new long long int*[n];
Don't use naked new. Either use smart pointers or - in this case - containers. What you want here is std::vector. There is absolutely zero speed penalty for using a vector rather than allocating an array yourself with new.
You don't free any of the memory you allocate. I don't know if that's tolerated in these coding competitions, but it is undefined behaviour in general. Here's a hot tip: If you are in a coding competition where it's okay to leak memory, and you want to save every cycle so you don't want to pay for freeing any memory, you can still use standard containers. All you need to do is define an allocator that doesn't delete. Which is just:
template <typename T>
struct leaking_allocator
{
using value_type = T;
auto allocate(std::size_t n) { return new T[n]; }
auto deallocate(T*, std::size_t) noexcept { }
};
If you'd used a vector, you wouldn't need both size and arr. You would just need auto A = std::vector<std::vector<long long int>{};. You would read n then do A.resize(n);. Then for each array you would read s and do A[i].resize(s);, and read the next s values into A[i][0] to A[i][s - 1]. The size of any array would be A[i].size().
And, of course, your program wouldn't leak (unless you deliberately made it do so by using a leaking allocator).
for(int i=1;i<=n;i++)
{
arr[i]=new long long int[n];
}
You have an out-of-bounds error here. You're lucky the program doesn't crash. I know the problem talks about 1-based arrays, but C++ arrays are 0-based. You need to do that conversion, either in your head or in the code.
So either:
for(int i = 0; i < n; ++i)
arr[i] = new long long int[n];
or:
for(int i = 1; i <= n; ++i)
arr[i - 1] = new long long int[n];
(Note: As Pete Kirkham points out, the above is still wrong. The allocation line should be moved to the next loop, after cin>>size[s];. And instead of allocating n elements, it should be allocating size[s]. The vector versions don't have this bug.)
In the next loop:
for(int i=1;i<=n;i++)
{
cin>>size[s];
for(int j=0;j<size[s];j++)
{
cin>>arr[i][j];
}
s++;
}
You have the same out-of-bounds error. But you also have a needless extra loop variable. Both i and s are doing the same thing here. And you never use s again after this loop. You could simplify this to:
for (int i = 0; i < n; ++i)
{
cin >> size[i];
for(int j = 0; j < size[i]; ++j)
cin >> arr[i][j];
}
But of course, if you used vectors, both of the above loops could simplify to:
auto A = std::vector<std::vector<long long int>>{}; // or, possibly, use leaking allocators here
auto n = 0;
std::cin >> n;
A.resize(n);
for (auto i = 0; i < A.size(); ++i)
{
auto s = 0;
std::cin >> s;
A[i].resize(s);
for (auto j = 0; j < A[i].size(); ++j)
std::cin >> A[i][j];
}
or even better and safer, using range-based loops:
auto A = std::vector<std::vector<long long int>>{}; // or, possibly, use leaking allocators here
auto n = 0;
std::cin >> n;
A.resize(n);
for (auto&& arr : A) // for each array in A
{
auto s = 0;
std::cin >> s;
arr.resize(s);
for (auto&& item : arr) // for each item in A[i]
std::cin >> item;
}
On to the calculation loop....
while(m--)
{
cin>>a>>b;
for(int i=1;i<=size[a];i++)
{
for(int j=0;j<size[b];j++)
sum=sum+fabs(arr[a][i]-arr[b][j]);
}
cout<<sum;
cout<<endl;
sum=0;
}
Once again, that first inner loop has an out-of-bounds error.
@vnp has already pointed out that you should be using std::abs(), not std::fabs(). But here are some more tips to increase speed and readability:
sum=sum+fabs(arr[a][i]-arr[b][j]);
can be simplified to:
sum += std::abs(arr[a][i] - arr[b][j]);
Because you've declared sum outside of the loop, you have to clear it on each iteration. That's a little brittle. It would be safer and more sensible to declare sum just before calculating the sum.
Also:
cout<<endl;
Never use endl. Especially in performance code. If you want a newline, just write a newline.
So the loop above becomes:
while (m--)
{
std::cin >> a >> b;
auto sum = 0LL;
for (int i = 0; i < size[a]; ++i)
{
for (int j = 0; j < size[b]; ++j)
sum += std::abs(arr[a][i] - arr[b][j]);
}
std::cout << sum << '\n';
}
And if you use vectors, the code is basically identical:
while(m--)
{
std::cin >> a >> b;
auto sum = 0LL;
for (int i = 0; i < A[a].size(); ++i)
{
for (int j = 0; j < A[b].size(); ++j)
sum += std::abs(A[a][i] - A[b][j]);
}
std::cout << sum << '\n';
}
or with range loops:
while(m--)
{
std::cin >> a >> b;
auto sum = 0LL;
for (auto item_a : A[a]) // for each item_a in A[a]
// (don't need && because they're just
// long long int, and we're just
// reading them)
{
for (auto item_b : A[b]) // for each item_b in A[b]
sum += std::abs(item_a - item_b);
}
std::cout << sum << '\n';
}
And finally:
return 0;
There's no need for this. main() returns zero automatically.
Summary
You have two critical problems in your code:
- You leak every array you allocate. If this is deliberate, at least document it with a comment. This problem would go away if you used smart pointers and containers. (But if you really want to leak, you can still use smart pointers and containers. You'd just need to use leaking deleters and allocators.)
- Many of your loops access out-of-bounds memory. The problem talks about 1-based arrays, but arrays in C++ are 0-based. You need to do that conversion.
You have one problem that will really hurt your efficiency:
- Don't use
endl.
And you have a few minor problems that are mostly stylistic:
- Don't declare variables until right before they're needed.
- Don't declare multiple variables all on one line.
- Don't use manual memory management - don't use naked
new/delete. Use containers and smart pointers. They are zero-cost abstractions.
- Space out your code. It's hard to spot errors when each line is just a jumble of symbols.
Some of the above will give you small speed boosts, but as @vnp noted, the real thing that's killing your time is that you didn't think the problem through, and just tried to brute-force it.
However, you have some serious bugs that you should worry about fixing first, before worrying about speed.
