Submission #1249338

#TimeUsernameProblemLanguageResultExecution timeMemory
1249338domiIdeal city (IOI12_city)C++20
0 / 100
4 ms1088 KiB
#include<bits/stdc++.h> using namespace std; const int64_t MOD = 1e9; int64_t n, ans; void dfs(int64_t nod, int64_t p, vector<vector<int64_t>>& T, vector<int64_t>& SZ, vector<int64_t>& s){ SZ[nod] = s[nod] - 1; for (auto &son : T[nod]) { if (son == p) continue; dfs(son, nod, T, SZ, s); SZ[nod] += SZ[son]; ans += (n - SZ[son]) * SZ[son]; } } int64_t solve(map<int64_t, vector<int64_t>>& mp) { vector<vector<int64_t>>T; map<pair<int64_t, int64_t>, int64_t>id; vector<int64_t>s; int64_t cnt = 0, idx = 0; for (auto &it : mp) { auto &v = it.first; auto &ap = it.second; sort(ap.begin(), ap.end()); ++idx; for (int64_t i = 0; i < ap.size(); ++i) { if (i == 0 || ap[i] != ap[i - 1] + 1) { ++cnt; T.push_back({}); s.push_back(0); } id[{v, ap[i]}] = cnt; ++s.back(); if (idx != 1 && id.find({v - 1, ap[i]}) != id.end() && (T[cnt].empty() || id[{v - 1, ap[i]}]) != T[cnt].back()) { T[cnt].push_back(id[{v - 1, ap[i]}]); T[id[{v - 1, ap[i]}]].push_back(cnt); } } } vector<int64_t>SZ(cnt + 1, 0); ans = 0; dfs(0, -1, T, SZ, s); return ans; } int DistanceSum(int N, int *X, int *Y) { n = N; map<int64_t, vector<int64_t>>lin, col; for (int64_t i = 0; i < N; ++i) { col[X[i]].push_back(Y[i]); lin[Y[i]].push_back(X[i]); } return (int)(solve(lin) + solve(col)) % 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...