Submission #872037

#TimeUsernameProblemLanguageResultExecution timeMemory
872037MatjazIdeal city (IOI12_city)C++14
32 / 100
99 ms856 KiB
#include<algorithm> #include <vector> #include <stdlib.h> #include <iostream> #include <queue> using namespace std; int DistanceSum(int N, int *X, int *Y) { if (N <= 2000){ vector<vector<int> > s(N, vector<int>()); for (int i=0;i<N;i++){ for (int j=i+1;j<N;j++){ if (abs(X[i] - X[j]) + abs(Y[i] - Y[j]) <= 1){ s[i].push_back(j); s[j].push_back(i); } } } long long M = 1000000000; long long sum = 0; for (int i=0;i<N;i++){ vector<int> d(N, N + 1); d[i] = 0; queue<int> Q; Q.push(i); while (!Q.empty()){ int x = Q.front(); Q.pop(); for (int i=0;i<s[x].size();i++){ if (d[s[x][i]] > d[x] + 1){ d[s[x][i]] = d[x] + 1; Q.push(s[x][i]); } } } for (int j=i+1;j<N;j++) sum = (sum + d[j]) % M; } return sum; } else { long long sum = 0; long long M = 1000000000; sort(X, X + N); sort(Y, Y + N); long long total = 0; for (int i=N-1;i>=0;i--){ sum = (sum + total - (N - 1 - i) * X[i]) % M; total += X[i]; } for (int i=N-1;i>=0;i--){ sum = (sum + total - (long long)(N - 1 - i) * Y[i]) % M; total += Y[i]; } return sum; } }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 for (int i=0;i<s[x].size();i++){
      |                              ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...