Submission #912890

#TimeUsernameProblemLanguageResultExecution timeMemory
912890Muhammad_AneeqIdeal city (IOI12_city)C++17
44 / 100
1048 ms8276 KiB
#include <cmath> #include <vector> #include <map> #include <algorithm> #include <queue> #include <iostream> using namespace std; long long const MAXN=1e5+10; vector<long long>nei[MAXN]={}; long long mod=1e9; long long ans=0; vector<long long>dx={0,0,-1,1},dy={-1,1,0,0}; long long dis[MAXN]={}; bool vis[MAXN]={}; void bfs(long long x) { queue<int>s; s.push(x); while (s.size()) { int y=s.front(); s.pop(); for (auto j:nei[y]) { if (!vis[j]) { dis[j]=dis[y]+1; vis[j]=1; s.push(j); } } } } int DistanceSum(int N, int X[], int Y[]) { map<long long,vector<long long>>d; map<pair<long long,long long>,long long>ex,cnt; for (long long i=0;i<N;i++) d[X[i]].push_back(Y[i]); bool subtask_3=1; for (auto& i:d) { sort(begin(i.second),end(i.second)); if (i.second.size()!=i.second.back()-i.second[0]+1) { subtask_3=0; break; } } if (subtask_3) { sort(Y,Y+N); sort(X,X+N); long long ans=0; long long szx=0,sux=0,szy=0,suy=0; for (long long i=0;i<N;i++) { long long g=1ll*Y[i]*szy-suy; g%=mod; ans=(ans+g)%mod; g=1ll*X[i]*szx-sux; g%=mod; ans=(ans+g)%mod; szy++; suy+=Y[i]; szx++; sux+=X[i]; } return ans; } for (int i=0;i<N;i++) { for (int j=0;j<N;j++) { if (abs(X[i]-X[j])+abs(Y[i]-Y[j])==1) nei[i].push_back(j); } } for (long long i=0;i<N;i++) dis[i]=0; for (long long i=0;i<N;i++) { bfs(i); for (long long j=i+1;j<N;j++) { dis[j]%=mod; ans=(ans+dis[j])%mod; } for (long long j=0;j<N;j++) dis[j]=vis[j]=0; } return ans; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:45:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wsign-compare]
   45 |   if (i.second.size()!=i.second.back()-i.second[0]+1)
      |       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...