Submission #879133

#TimeUsernameProblemLanguageResultExecution timeMemory
879133YongXinIdeal city (IOI12_city)C++14
0 / 100
1076 ms5760 KiB
#include <bits/stdc++.h> #define ll long long #define pll pair<ll,ll> using namespace std; int DistanceSum(int n,int*X,int*Y){ ll x=0,y=0,maxx=0,maxy=0,minx=9e18,miny=9e18,r=0; vector<pll>vx,vy; queue<pll>q; pll a[n]; pair<int,int>temp[n]; for(ll i=0;i<n;++i){ temp[i]=make_pair(X[i],Y[i]); maxx=max(maxx,(ll)temp[i].first); maxy=max(maxy,(ll)temp[i].second); minx=min(minx,(ll)temp[i].first); miny=min(miny,(ll)temp[i].second); } sort(temp,temp+n); maxx-=minx-1; maxy-=miny-1; pll arr[maxy][maxx]; memset(arr,-1,16*maxy*maxx); for(ll i=0;i<n;++i){ temp[i].first-=minx; temp[i].second-=miny; if(temp[i].first!=0&&arr[temp[i].first-1][temp[i].second].first!=-1)a[i].first=arr[temp[i].first-1][temp[i].second].first; else{ a[i].first=x; ++x; } if(temp[i].second!=0&&arr[temp[i].first][temp[i].second-1].second!=-1)a[i].second=arr[temp[i].first][temp[i].second-1].second; else{ a[i].second=y; ++y; } arr[temp[i].first][temp[i].second]=a[i]; if(temp[i].first!=0&&arr[temp[i].first-1][temp[i].second].first!=-1)vy.push_back(make_pair(arr[temp[i].first-1][temp[i].second].second,a[i].second)); if(temp[i].second!=0&&arr[temp[i].first][temp[i].second-1].second!=-1)vx.push_back(make_pair(arr[temp[i].first][temp[i].second-1].first,a[i].first)); } ll nx[x],ny[y]; bool visitx[x],visity[y]; vector<ll>adjx[x],adjy[y]; memset(nx,0,8*x); memset(ny,0,8*y); for(ll i=0;i<n;++i){ ++nx[a[i].first]; ++ny[a[i].second]; } sort(vx.begin(),vx.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end()); sort(vy.begin(),vy.end()); vy.erase(unique(vy.begin(),vy.end()),vy.end()); for(ll i=0;i<vx.size();++i){ adjx[vx[i].first].push_back(vx[i].second); adjx[vx[i].second].push_back(vx[i].first); } for(ll i=0;i<vy.size();++i){ adjy[vy[i].first].push_back(vy[i].second); adjy[vy[i].second].push_back(vy[i].first); } for(ll i=0;i<x;++i){ memset(visitx,-1,x); q.push(make_pair(i,0)); while(!q.empty()){ if(visitx[q.front().first]){ if(q.front().first>i)r+=q.front().second*nx[i]*nx[q.front().first]; visitx[q.front().first]=false; for(ll j=0;j<adjx[q.front().first].size();++j)q.push(make_pair(adjx[q.front().first][j],q.front().second+1)); } q.pop(); } } for(ll i=0;i<y;++i){ memset(visity,-1,y); q.push(make_pair(i,0)); while(!q.empty()){ if(visity[q.front().first]){ if(q.front().first>i)r+=q.front().second*ny[i]*ny[q.front().first]; visity[q.front().first]=false; for(ll j=0;j<adjy[q.front().first].size();++j)q.push(make_pair(adjy[q.front().first][j],q.front().second+1)); } q.pop(); } } return(int)(r%(int)1e9); }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(ll i=0;i<vx.size();++i){
      |                ~^~~~~~~~~~
city.cpp:57:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(ll i=0;i<vy.size();++i){
      |                ~^~~~~~~~~~
city.cpp:68:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(ll j=0;j<adjx[q.front().first].size();++j)q.push(make_pair(adjx[q.front().first][j],q.front().second+1));
      |                            ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:80:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 for(ll j=0;j<adjy[q.front().first].size();++j)q.push(make_pair(adjy[q.front().first][j],q.front().second+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...