Submission #768001

#TimeUsernameProblemLanguageResultExecution timeMemory
768001boris_mihovIdeal city (IOI12_city)C++17
0 / 100
38 ms8196 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <queue> #include <map> typedef long long llong; const int MAXN = 100000 + 10; const int MOD = 1'000'000'000; int n; llong ans; int sz[MAXN]; int par[MAXN]; llong dp[MAXN]; int x[MAXN], y[MAXN]; std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; std::map <std::pair <int,int>, int> map; std::vector <int> g[MAXN]; std::vector <int> t[MAXN]; std::queue <int> q; void dfsDown(int node) { dp[node] = 0; sz[node] = 1; for (const int &u : t[node]) { if (u == par[node]) { continue; } dfsDown(u); sz[node] += sz[u]; dp[node] += dp[u] + sz[u]; } } void dfsUp(int node) { std::vector <std::pair <int*, int>> rollback; if (node != 1) { dp[node] = dp[par[node]] + n - 2 * sz[node]; for (const int &u : g[node]) { if (par[u] != node) { rollback.push_back({&par[u], par[u]}); if (u != par[node] && par[par[u]] == par[node]) dp[node] -= 2 * sz[u]; par[u] = node; } } } for (const int &u : t[node]) { if (u != par[node]) { dfsUp(u); } } for (auto [addr, val] : rollback) { *addr = val; } } int DistanceSum(int N, int *X, int *Y) { n = N; for (int i = 1 ; i <= n ; ++i) { x[i] = X[i - 1]; y[i] = Y[i - 1]; map[{x[i], y[i]}] = i; } for (int i = 1 ; i <= n ; ++i) { for (const auto &[dx, dy] : delta) { if (map.count({x[i] + dx, y[i] + dy})) { g[i].push_back(map[{x[i] + dx, y[i] + dy}]); } } } q.push(1); par[1] = 0; std::fill(par + 2, par + n + 1, -1); while (!q.empty()) { int top = q.front(); q.pop(); for (const int &i : g[top]) { if (par[i] == -1) { par[i] = top; t[top].push_back(i); q.push(i); } } } dfsDown(1); dfsUp(1); for (int i = 1 ; i <= n ; ++i) { ans += dp[i]; ans %= MOD; } assert(ans % 2 == 0); return ans / 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...