Submission #59241

#TimeUsernameProblemLanguageResultExecution timeMemory
59241TadijaSebezIdeal city (IOI12_city)C++11
100 / 100
617 ms29024 KiB
#include <stdio.h> #include <vector> #include <algorithm> #include <map> using namespace std; #define mp make_pair #define pb push_back #define ll long long const int N=100050; const int mod=1e9; int comp[N],cnt; map<pair<int,int> ,int> id; vector<int> E[N]; int weg[N],sz[N],n; int x[N],y[N],p[N]; void init(){ for(int i=0;i<N;i++) p[i]=i;} int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);} void Union(int x, int y){ p[Find(x)]=Find(y);} int dep[N]; ll ans; void DFS(int u, int p) { int i; //printf("DFS:%i %i\n",u,p); sz[u]=weg[u]; dep[u]=dep[p]+1; for(i=0;i<E[u].size();i++) { int v=E[u][i]; if(v!=p) DFS(v,u),sz[u]+=sz[v]; } ll mul=0; //int sub=0; for(i=0;i<E[u].size();i++) { int v=E[u][i]; if(v!=p) { mul+=(ll)sz[v]*(sz[u]-sz[v])%mod; mul%=mod; //sub+=sz[v]; } } mul+=(ll)weg[u]*(weg[u]-1)%mod; mul%=mod; ans-=(ll)mul*dep[u]%mod; if(ans<0) ans+=mod; ans+=(ll)(n-sz[u]+weg[u]-1)*weg[u]%mod*dep[u]%mod; ans%=mod; //printf("u:%i -mul:%lld +mul:%lld weg:%lld sz:%lld\n",u,mul,(n-sz[u]+weg[u]-1)*weg[u],weg[u],sz[u]); } int SolveTree() { ans=0; DFS(1,0); return ans%mod; } int DistanceSum(int M, int X[], int Y[]) { n=M; int i,j; for(i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1]; for(i=1;i<=n;i++) id[mp(x[i],y[i])]=i; for(i=1;i<=n;i++) { if(!comp[i]) { cnt++; comp[i]=cnt; weg[cnt]=1; j=1; while(id.count(mp(x[i],y[i]+j))) comp[id[mp(x[i],y[i]+j)]]=cnt,j++,weg[cnt]++; j=1; while(id.count(mp(x[i],y[i]-j))) comp[id[mp(x[i],y[i]-j)]]=cnt,j++,weg[cnt]++; } } //for(i=1;i<=n;i++) printf("%i ",comp[i]);printf("\n"); //for(i=1;i<=cnt;i++) printf("%i ",weg[i]);printf("\n"); init(); for(i=1;i<=n;i++) { int u=id[mp(x[i]+1,y[i])]; if(u && Find(comp[i])!=Find(comp[u])) { //printf("(%i - %i)\n",comp[i],comp[u]); E[comp[i]].pb(comp[u]); E[comp[u]].pb(comp[i]); Union(comp[i],comp[u]); } u=id[mp(x[i]-1,y[i])]; if(u && Find(comp[i])!=Find(comp[u])) { //printf("(%i - %i)\n",comp[i],comp[u]); E[comp[i]].pb(comp[u]); E[comp[u]].pb(comp[i]); Union(comp[i],comp[u]); } } int sol=SolveTree(); //printf("->%i\n",sol); for(i=1;i<=n;i++) comp[i]=0; for(i=1;i<=cnt;i++) E[i].clear(); cnt=0; for(i=1;i<=n;i++) { if(!comp[i]) { cnt++; comp[i]=cnt; weg[cnt]=1; j=1; while(id[mp(x[i]+j,y[i])]) comp[id[mp(x[i]+j,y[i])]]=cnt,j++,weg[cnt]++; j=1; while(id[mp(x[i]-j,y[i])]) comp[id[mp(x[i]-j,y[i])]]=cnt,j++,weg[cnt]++; } } //for(i=1;i<=n;i++) printf("%i ",comp[i]);printf("\n"); init(); for(i=1;i<=n;i++) { int u=id[mp(x[i],y[i]+1)]; if(u && Find(comp[i])!=Find(comp[u])) { //printf("(%i - %i)\n",comp[i],comp[u]); E[comp[i]].pb(comp[u]); E[comp[u]].pb(comp[i]); Union(comp[i],comp[u]); } u=id[mp(x[i],y[i]-1)]; if(u && Find(comp[i])!=Find(comp[u])) { //printf("(%i - %i)\n",comp[i],comp[u]); E[comp[i]].pb(comp[u]); E[comp[u]].pb(comp[i]); Union(comp[i],comp[u]); } } sol+=SolveTree(); sol%=mod; return sol; }

Compilation message (stderr)

city.cpp: In function 'void DFS(int, int)':
city.cpp:27:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].size();i++)
          ~^~~~~~~~~~~~
city.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<E[u].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...