Submission #768026

#TimeUsernameProblemLanguageResultExecution timeMemory
768026boris_mihovIdeal city (IOI12_city)C++17
32 / 100
36 ms11220 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]; llong chain[MAXN]; int inChain[MAXN]; int x[MAXN], y[MAXN]; std::vector <int> out[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]; dp[node] %= MOD; } } void dfsUp(int node) { if (node != 1) { dp[node] = (dp[par[node]] + n + 2 * (MOD - chain[inChain[node]])) % MOD; } for (const int &u : t[node]) { if (u != par[node]) { dfsUp(u); } } } int timer; void dfsChain(int node) { inChain[node] = timer; chain[inChain[node]] += sz[node]; chain[inChain[node]] %= MOD; for (const int &u : out[node]) { if (inChain[u] == 0) { dfsChain(u); } } } 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); } else if (par[i] != top && par[top] != i) { out[top].push_back(i); } } } dfsDown(1); for (int i = 1 ; i <= n ; ++i) { if (inChain[i] == 0) { timer++; dfsChain(i); } } dfsUp(1); for (int i = 1 ; i <= n ; ++i) { ans += dp[i]; assert(dp[i] >= 0 && dp[i] < MOD); ans %= MOD; } 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...