Submission #73645

#TimeUsernameProblemLanguageResultExecution timeMemory
73645FLDutchmanIdeal city (IOI12_city)C++14
100 / 100
661 ms33192 KiB
#include <bits/stdc++.h> using namespace std; typedef int INT; #define pb push_back #define int long long #define fst first #define snd second #define FOR(i,l,r) for(int i = (l); i < (r); i++) typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef vector<ii> vii; struct edge{ int v, i; }; int N; vii points; vvi adj; map<ii, int> idx; vvi rowgr, colgr; vii ce, re; vector<vector<edge>> rg, cg; vi rowsz, colsz; vi row, col; vi vis; void flood(int u, int c, bool co){ vis[u] = 1; if(co) col[u] = c, colsz[c] ++; else row[u] = c, rowsz[c] ++; for(int i = co; i < 4; i+= 2) if(adj[u][i] != -1 and !vis[adj[u][i]]) flood(adj[u][i], c, co); for(int i = 1-co; i < 4; i+= 2) if(adj[u][i] != -1 and vis[adj[u][i]]) { int v = adj[u][i]; if(v == -1) continue; if(co) colgr[c].pb(col[v]), colgr[col[v]].pb(c); else rowgr[c].pb(row[v]), rowgr[row[v]].pb(c); } } int dp[200000][2]; int dfs(int e, int u, int p, bool col){ int &res = dp[e][col]; if(res != 0) return res; res = col ? colsz[u] : rowsz[u]; for(edge E : (col ? cg[u] : rg[u]) ) if(E.v != p) res += dfs(E.i, E.v, u, col); return res; } int dfs(int u, int p, int col){ //cout << u << " " << p << " " << col << endl; if(col) { int e = lower_bound(ce.begin(), ce.end(), make_pair(p, u))-ce.begin(); //cout << (ce[e] == make_pair(u,p)) << endl; return dfs(e, u, p, col); } else { int e = lower_bound(re.begin(),re.end(), make_pair(p,u)) -re.begin(); //cout << (re[e] == make_pair(u,p)) << endl; return dfs(e,u,p,col); } } int gettot(int u, int tot){ //cout << u << " " << tot << endl; int res = tot; vis[u] = 1; FOR(i, 0, 4){ int v = adj[u][i]; if(v == -1 || vis[v]) continue; if(i % 2 == 0) { res += gettot(v, tot - 2*dfs(col[v], col[u], 1) + N); } else res += gettot(v, tot - 2*dfs(row[v], row[u], 0) + N); } return res; } int bfs(int u){ vis.assign(N, 0); int total = 0; queue<ii> q; q.push({u, 0}); vis[u] = 1; while(!q.empty()){ ii p = q.front(); q.pop(); total += p.snd; for(int v : adj[p.fst])if(v !=-1 and !vis[v]){ q.push({v,p.snd+1}); vis[v] = 1; } } vis.assign(N, 0); return total; } INT DistanceSum(INT n, INT *X, INT *Y) { FOR(i,0,200000) FOR(j,0,2) dp[i][j] = 0; N = n; adj.assign(N, vi(4, -1)); FOR(i, 0, N) {points.pb({X[i], Y[i]}); idx[{X[i], Y[i]}] = i+1;} FOR(i, 0, N){ int x = X[i], y = Y[i]; int neigh; if(neigh = idx[{x+1, y}]) adj[i][0] = neigh-1; if(neigh = idx[{x, y-1}]) adj[i][1] = neigh-1; if(neigh = idx[{x-1, y}]) adj[i][2] = neigh-1; if(neigh = idx[{x, y+1}]) adj[i][3] = neigh-1; } idx.clear(); int k = 0; row.assign(N, -1); col.assign(N, -1); vis.assign(N, 0); FOR(i, 0, N) if(!vis[i]){ rowgr.pb(vi(0)); rowsz.pb(0); flood(i, k++,0); } for(auto &v : rowgr){ sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } k = 0; vis.assign(N, 0); FOR(i, 0, N) if(!vis[i]){ colgr.pb(vi(0)); colsz.pb(0); flood(i, k++,1); } vis.assign(N, 0); for(auto &v : colgr){ sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); } rg.resize(rowgr.size()); cg.resize(colgr.size()); int i = 0; FOR(u, 0, rowgr.size()){ FOR(v, 0, rowgr[u].size()){ rg[u].pb({rowgr[u][v], i++}); re.pb({u, rowgr[u][v]}); } } i = 0; FOR(u, 0, colgr.size()){ FOR(v, 0, colgr[u].size()){ cg[u].pb({colgr[u][v], i++}); ce.pb({u, colgr[u][v]}); } } /* cout<<i<<endl; for(auto &v : adj) { for(int k : v) cout << k << " "; cout<<endl; } for(auto &v : colgr) { for(int k : v) cout << k << " "; cout<<endl; } cout<<endl; for(auto &v : rowgr) { for(int k : v) cout << k << " "; cout<<endl; } for(int k : col) cout << k << " "; cout<<endl; for(int k : row) cout << k << " "; cout<<endl; cout << dfs(1, 0, 0) << endl; cout << bfs(4) <<endl; cout << "bfs " + to_string(dfs(3,4,1)) <<endl; */ return (gettot(0, bfs(0))/2) % 1000000000; } /*-1 -1 -1 1 3 0 -1 -1 4 -1 -1 -1 7 -1 1 -1 8 -1 2 5 9 4 -1 6 -1 5 -1 7 10 6 3 -1 -1 -1 4 9 -1 8 5 -1 -1 -1 7 -1 2 3 0 3 1 2 4 5 3 3 1 0 4 3 2 4 1 3 0 0 1 2 3 3 3 3 4 4 5 0 1 2 1 2 3 4 1 2 3 1 10 45 0 45 1 36 3 29 7 24 10 33 5 3 6 23 5 24 9 31 8 36 4 29 2 38 1 3 3 4 4 3 3 2 2 0 */

Compilation message (stderr)

city.cpp: In function 'INT DistanceSum(INT, INT*, INT*)':
city.cpp:109:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x+1, y}]) adj[i][0] = neigh-1;
city.cpp:110:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x, y-1}]) adj[i][1] = neigh-1;
city.cpp:111:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x-1, y}]) adj[i][2] = neigh-1;
city.cpp:112:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x, y+1}]) adj[i][3] = neigh-1;
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
city.cpp:148:2: note: in expansion of macro 'FOR'
  FOR(u, 0, rowgr.size()){
  ^~~
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
city.cpp:149:3: note: in expansion of macro 'FOR'
   FOR(v, 0, rowgr[u].size()){
   ^~~
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
city.cpp:156:2: note: in expansion of macro 'FOR'
  FOR(u, 0, colgr.size()){
  ^~~
city.cpp:10:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,l,r) for(int i = (l); i < (r); i++)
                                       ^
city.cpp:157:3: note: in expansion of macro 'FOR'
   FOR(v, 0, colgr[u].size()){
   ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...