Submission #912860

#TimeUsernameProblemLanguageResultExecution timeMemory
912860Muhammad_AneeqIdeal city (IOI12_city)C++17
44 / 100
1049 ms19012 KiB
#include <cmath> #include <vector> #include <map> #include <algorithm> #include <queue> #include <iostream> using namespace std; int const MAXN=1e5+10; vector<pair<int,int>>nei[MAXN]={}; int mod=1e9; long long ans=0; vector<int>dx={0,0,-1,1},dy={-1,1,0,0}; int dis[MAXN]={}; void bfs(int x) { priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; pq.push({0,x}); dis[x]=0; while (pq.size()) { auto y=pq.top(); pq.pop(); for (auto [j,w]:nei[y.second]) { if (dis[j]>y.first+w) { dis[j]=y.first+w; pq.push({dis[j],j}); } } } } int DistanceSum(int N, int X[], int Y[]) { map<int,vector<int>>d; map<pair<int,int>,vector<int>>ex; pair<int,int>a[N]; int minX=1e9+10,minY=1e9+10; for (int i=0;i<N;i++) { minX=min(minX,X[i]);minY=min(minY,Y[i]); } for (int i=0;i<N;i++) { X[i]-=minX; Y[i]-=minY; a[i]={X[i],Y[i]}; ex[{X[i],Y[i]}].push_back(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); int ans=0; long long szx=0,sux=0,szy=0,suy=0; for (int 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 (auto i:ex) { int x=i.first.first,y=i.first.second; for (int j=0;j<4;j++) { if (ex.find({x+dx[j],y+dy[j]})!=ex.end()) { for (auto k:i.second) for (auto l:ex[{x+dx[j],y+dy[j]}]) nei[k].push_back({l,1}); for (int k=0;k<i.second.size();k++) for (int l=k+1;l<i.second.size();l++) { nei[i.second[k]].push_back({i.second[l],0}); nei[i.second[l]].push_back({i.second[k],0}); } } } } for (int i=0;i<N;i++) dis[i]=1e9+10; for (int i=0;i<N;i++) { bfs(i); for (int j=i+1;j<N;j++) ans=(ans+dis[j])%mod; for (int j=0;j<N;j++) dis[j]=1e9+10; } return ans; }

Compilation message (stderr)

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