Submission #304700

#TimeUsernameProblemLanguageResultExecution timeMemory
304700HeheheIdeal city (IOI12_city)C++14
0 / 100
99 ms14968 KiB
#include <bits/stdc++.h> #define DIM 100010 #define INF 2000000000 #define MOD 1000000000 using namespace std; map <pair<int,int>,int> a; set <int> L[DIM],L2[DIM]; deque <int> c; pair <int,int> v[DIM]; int what_comp[DIM],Size[DIM],Size2[DIM],sum[DIM],sum2[DIM],viz[DIM]; int nr_nodes; int di[] = {-1,1,0,0}; int dj[] = {0,0,-1,1}; void dfs (int nod, int tata){ sum[nod] = Size[nod]; for (auto vecin : L[nod]) if (vecin != tata){ dfs (vecin,nod); sum[nod] += sum[vecin]; }} void dfs2 (int nod, int tata){ sum2[nod] = Size2[nod]; for (auto vecin : L2[nod]) if (vecin != tata){ dfs2 (vecin,nod); sum2[nod] += sum2[vecin]; }} int DistanceSum (int n, int *X, int *Y){ int i; long long sol = 0; for (i=1;i<=n;i++){ v[i] = make_pair (X[i-1],Y[i-1]); a[v[i]] = i; } int k = 0; //horizontal for(int i = 1; i <= n; i++){ if(viz[i])continue; viz[i] = 1; what_comp[i] = ++k; int cnt = 0; int x = X[i - 1], y = Y[i - 1]; while(a[{x, y + 1}]){ y++; int idx = a[{x, y}]; what_comp[idx] = k; viz[idx] = 1; cnt++; } y = Y[i - 1]; while(a[{x, y - 1}]){ y--; int idx = a[{x, y}]; what_comp[idx] = k; viz[idx] = 1; cnt++; } Size[k] = ++cnt; } for(int i = 1; i <= n; i++){ int I = X[i - 1], J = Y[i - 1]; int now = what_comp[i]; for(int l = 0; l < 4; l++){ int x = I + di[l], y = J + dj[l]; if(!a[{x, y}])continue; int next = what_comp[a[{x, y}]]; if(now == next)continue; L[now].insert(next); L[next].insert(now); } } dfs(1, 0); for (i=1;i<=nr_nodes;i++) sol += 1LL * sum[i] * (n - sum[i]); memset(viz, 0, sizeof(viz)); memset(what_comp, 0, sizeof(what_comp)); nr_nodes = 0; /// verticala for (i=1;i<=n;i++){ if (!viz[i]){ viz[i] = 1; what_comp[i] = ++nr_nodes; int x = v[i].first, y = v[i].second, cnt = 1; while (a[make_pair(x-1,y)]){ x--, cnt++; int idx = a[make_pair(x,y)]; viz[idx] = 1; what_comp[idx] = nr_nodes; } x = v[i].first; while (a[make_pair(x+1,y)]){ x++, cnt++; int idx = a[make_pair(x,y)]; viz[idx] = 1; what_comp[idx] = nr_nodes; } Size2[nr_nodes] = cnt; } } for (i=1;i<=n;i++){ int ic = v[i].first, jc = v[i].second; int x = what_comp[i]; for (int dir=0;dir<=3;dir++){ int iv = ic + di[dir]; int jv = jc + dj[dir]; int idx = a[make_pair(iv,jv)]; if (!idx) continue; int y = what_comp[idx]; if (x != y){ L2[x].insert(y); L2[y].insert(x); }}} dfs2 (1,0); for (i=1;i<=nr_nodes;i++) sol += 1LL * sum2[i] * (n - sum2[i]); return sol % 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...