Submission #56740

#TimeUsernameProblemLanguageResultExecution timeMemory
56740RezwanArefin01Ideal city (IOI12_city)C++17
100 / 100
453 ms24628 KiB
#include <bits/stdc++.h> using namespace std; const int mod = 1e9; const int M = 1e5 + 10; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, -1, 1}; vector<int> adj[M]; int comp[M], w[M], sub[M]; int ans = 0; void dfs(int u, int par) { sub[u] = w[u]; for(int v : adj[u]) if(v - par) { dfs(v, u); sub[u] += sub[v]; if(sub[u] >= mod) sub[u] -= mod; } } void solve(int N, int *X, int *Y) { vector<pair<int, int> > v; map<pair<int, int>, int> mp; for(int i = 0; i < N; i++) v.emplace_back(X[i], Y[i]); sort(v.begin(), v.end()); for(int i = 0; i < N; i++) mp[{v[i].first, v[i].second}] = i; int idx = 0; for(int i = 0; i < N; ) { int x = v[i].first, j = i + 1; comp[i] = idx; while(j < N && v[j].second == v[j - 1].second + 1) comp[j++] = idx; w[idx++] = j - i; i = j; } set<pair<int, int> > st; for(int i = 0; i < N; i++) { int x = v[i].first, y = v[i].second; for(int j = 0; j < 4; j++) { int xx = x + dx[j], yy = y + dy[j]; if(mp.count({xx, yy})) { int a = comp[i], b = comp[mp[{xx, yy}]]; if(a > b) swap(a, b); if(a != b) st.insert({a, b}); } } } for(int i = 0; i < idx; i++) adj[i].clear(); for(auto it : st) { int u = it.first, v = it.second; adj[u].push_back(v); adj[v].push_back(u); } dfs(0, -1); for(int i = 1; i < idx; i++) { ans += sub[i] * 1ll * (N - sub[i]) % mod; if(ans >= mod) ans -= mod; } } int DistanceSum(int N, int *X, int *Y) { solve(N, X, Y); solve(N, Y, X); return ans; }

Compilation message (stderr)

city.cpp: In function 'void solve(int, int*, int*)':
city.cpp:36:13: warning: unused variable 'x' [-Wunused-variable]
         int x = v[i].first, j = i + 1; 
             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...