제출 #103349

#제출 시각아이디문제언어결과실행 시간메모리
103349popovicirobert이상적인 도시 (IOI12_city)C++14
55 / 100
372 ms29236 KiB
#include <bits/stdc++.h> using namespace std; typedef pair <int, int> PII; typedef vector <int> VI; typedef vector <VI> VVI; const int MOD = (int) 1e9; inline void mod(int &x) { if(x >= MOD) x -= MOD; } int dfs(int nod, int par, VVI &g, VI &w, VI &lvl, VI &sp) { lvl[nod] = lvl[par] + 1, sp[nod] = 0; int ans = 0; for(auto it : g[nod]) { if(lvl[it] == 0) { ans += dfs(it, nod, g, w, lvl, sp); sp[nod] += sp[it]; mod(sp[nod]); } } ans = (ans + 2LL * w[nod] * sp[nod] * lvl[nod]) % MOD; for(auto it : g[nod]) { if(lvl[it] == lvl[nod] + 1) { ans = (ans + 1LL * (sp[nod] - sp[it] + MOD) * lvl[nod] * sp[it]) % MOD; } } sp[nod] += w[nod]; mod(sp[nod]); return ans; } inline int solve(int N, int *X, int *Y, VVI &cx, VVI &cy, VI &nrm_x, VI &nrm_y) { map <PII, int> mp, vis; VVI g(N + 1); VI w(N + 1); int i, cur = 0; for(int x = 1; x <= N; x++) { sort(cx[x].begin(), cx[x].end()); int sz = cx[x].size(); i = 0; while(i < sz) { int j = i; cur++; while(j < sz && cx[x][i] + j - i == cx[x][j]) { auto it = mp[{nrm_x[x] - 1, cx[x][j]}]; if(it != 0) { if(vis[{it, cur}] == 0) { g[cur].push_back(it); g[it].push_back(cur); vis[{it, cur}] = vis[{cur, it}] = 1; } } it = mp[{nrm_x[x] + 1, cx[x][j]}]; if(it != 0) { if(vis[{it, cur}] == 0) { g[cur].push_back(it); g[it].push_back(cur); vis[{it, cur}] = vis[{cur, it}] = 1; } } w[cur]++; mp[{nrm_x[x], cx[x][j]}] = cur; j++; } i = j; } } VI lvl(N + 1), sp(N + 1); int aux = dfs(1, 0, g, w, lvl, sp); int ans = 0; for(i = 1; i <= cur; i++) { ans = (ans + 1LL * w[i] * lvl[i] * (N - w[i])) % MOD; } mod(aux); ans += MOD - aux; mod(ans); return ans; } int DistanceSum(int N, int *X, int *Y) { VVI cx(N + 1), cy(N + 1); VI nrm_x(N + 1), nrm_y(N + 1); map <int, int> mpx, mpy; int curx = 0, cury = 0; for(int i = 0; i < N; i++) { if(mpx[X[i]] == 0) { curx++; mpx[X[i]] = curx; nrm_x[curx] = X[i]; } if(mpy[Y[i]] == 0) { cury++; mpy[Y[i]] = cury; nrm_y[cury] = Y[i]; } cx[mpx[X[i]]].push_back(Y[i]); cy[mpy[Y[i]]].push_back(X[i]); } int ans = solve(N, X, Y, cx, cy, nrm_x, nrm_y); ans += solve(N, Y, X, cy, cx, nrm_y, nrm_x); mod(ans); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...