Submission #71169

#TimeUsernameProblemLanguageResultExecution timeMemory
71169MANcityIdeal city (IOI12_city)C++14
100 / 100
731 ms56456 KiB
#include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<set> #include<stack> #include<string> #include<cstring> #include<vector> using namespace std; #define for1(i,n) for(int i=1;i<=(int)n;i++) #define for0(i,n) for(int i=0;i<=(int)n;i++) #define forn(i,n) for(int i=n;i>=1;i--) #define fo(i,x,y) for(int i=x;i<=(int)y;i++) #define fr(i,x,y) for(int i=x;i>=(int)y;i--) #define pb push_back #define mp make_pair #define LL long long const LL Mod=1000*1000*1000+7; const LL maMod=1000*1000*1000; int N; int X[200002]; int Y[200002]; vector<vector<int> > gh(100002); vector<vector<int> > gv(100002); int w_h[100002]; int w_v[100002]; pair<int,pair<int,int> > Sx[100002]; pair<int,pair<int,int> > Sy[100002]; int tree_h[100002]; int tree_v[100002]; int qan_h; int qan_v; map<pair<int,int>,int> map_h; map<pair<int,int>,int> map_v; map<pair<int,int>,int> kp_v; map<pair<int,int>,int> kp_h; void edge(int x,int y,int val) { if(y==0 || x==0) return; if(x==y) return; if(val==2 && kp_v[{x,y}]==0 && kp_v[{y,x}]==0) { kp_v[{x,y}]=1; gv[x].push_back(y); gv[y].push_back(x); } if(val==1 && kp_h[{x,y}]==0 && kp_h[{y,x}]==0) { kp_h[{x,y}]=1; gh[x].push_back(y); gh[y].push_back(x); } } void connect(int x,int y,int val) { int G=map_h[{x,y}]; edge(G,map_h[{x-1,y}],1); edge(G,map_h[{x+1,y}],1); edge(G,map_h[{x,y-1}],1); edge(G,map_h[{x,y+1}],1); G=map_v[{x,y}]; edge(G,map_v[{x-1,y}],2); edge(G,map_v[{x+1,y}],2); edge(G,map_v[{x,y-1}],2); edge(G,map_v[{x,y+1}],2); } LL SUM_H; LL SUM_V; LL vsum[1000002]; LL hsum[1000002]; LL ANS; void dfs_h(int v,int p) { for0(i,gh[v].size()-1) { int to=gh[v][i]; if(to!=p) { dfs_h(to,v); hsum[v]=(hsum[v]+hsum[to])%maMod; ANS=((LL)ANS+(LL)(SUM_H-hsum[to])*(LL)hsum[to])%maMod; } } hsum[v]=(hsum[v]+w_h[v])%maMod; } void dfs_v(int v,int p) { for0(i,gv[v].size()-1) { int to=gv[v][i]; if(to!=p) { dfs_v(to,v); vsum[v]=(vsum[v]+vsum[to])%maMod; ANS=((LL)ANS+(LL)(SUM_V-vsum[to])*(LL)vsum[to])%maMod; } } vsum[v]=(vsum[v]+w_v[v])%maMod; } int DistanceSum(int N_0, int *X_0, int *Y_0) { N=N_0; for0(i,N-1) X[i]=X_0[i]; for0(i,N-1) Y[i]=Y_0[i]; for0(i,N-1) Sx[i]={X[i],{Y[i],i}}; for0(i,N-1) Sy[i]={Y[i],{X[i],i}}; Sx[N]={-1,{-1,-1}}; sort(Sx,Sx+N+1); for1(i,N) { int x_now=Sx[i].first; int x_bef=Sx[i-1].first; int y_now=Sx[i].second.first; int y_bef=Sx[i-1].second.first; if(x_now!=x_bef || (y_now!=(y_bef+1))) { qan_v++; } w_v[qan_v]++; map_v[{x_now,y_now}]=qan_v; connect(x_now,y_now,2); } Sy[N]={-1,{-1,-1}}; sort(Sy,Sy+N+1); for1(i,N) { int x_now=Sy[i].second.first; int x_bef=Sy[i-1].second.first; int y_now=Sy[i].first; int y_bef=Sy[i-1].first; if(y_now!=y_bef || (x_now!=(x_bef+1))) { qan_h++; } w_h[qan_h]++; map_h[{x_now,y_now}]=qan_h; connect(x_now,y_now,1); } for1(i,qan_h) SUM_H=(SUM_H+w_h[i])%maMod; for1(i,qan_v) SUM_V=(SUM_V+w_v[i])%maMod; dfs_h(1,0); dfs_v(1,0); return ANS; } /* 11 2 5 2 6 3 3 3 6 4 3 4 4 4 5 4 6 5 3 5 4 5 6 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...