Submission #1024394

#TimeUsernameProblemLanguageResultExecution timeMemory
1024394socpiteIdeal city (IOI12_city)C++17
100 / 100
133 ms23136 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; const int mod = 1e9; vector<int> g[maxn]; int W[maxn]; long long dfs(int x, int p, int N){ long long re = 0; for(auto v: g[x]){ if(v == p)continue; re += dfs(v, x, N); W[x] += W[v]; } re += 1LL*W[x]*(N - W[x])%mod; re %= mod; return re; } long long solve(int N, int *X, int *Y){ for(int i = 1; i <= N; i++){ g[i].clear(); W[i] = 0; } int cnt = 0; map<int, set<int>> mp; map<pair<int, int>, int> id; for(int i = 0; i < N; i++)mp[X[i]].insert(Y[i]); for(auto v: mp){ int prv = -2; for(auto pos: v.second){ if(pos == prv + 1)id[{v.first, pos}] = cnt; else id[{v.first, pos}] = ++cnt; W[cnt]++; if(id.find({v.first-1, pos}) != id.end()){ int prvid = id[{v.first-1, pos}]; g[cnt].push_back(prvid); g[prvid].push_back(cnt); } prv = pos; } } for(int i = 1; i <= cnt; i++){ sort(g[i].begin(), g[i].end()); g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end()); } return dfs(1, 0, N); } int DistanceSum(int N, int *X, int *Y) { long long ans = solve(N, X, Y); for(int i = 0; i < N; i++)swap(X[i], Y[i]); ans += solve(N, X, Y); return ans%mod; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...