제출 #304680

#제출 시각아이디문제언어결과실행 시간메모리
304680Hehehe이상적인 도시 (IOI12_city)C++14
100 / 100
977 ms33852 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],what_comp2[DIM],Size[DIM],Size2[DIM],sum[DIM],sum2[DIM],viz[DIM]; int nr_nodes, nr_nodes2; 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; } /// grupez celulele pe orizontala si pe verticala si o sa am 2 arbori /// orizontala 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,y+1)]){ y++, cnt++; int idx = a[make_pair(x,y)]; viz[idx] = 1; what_comp[idx] = nr_nodes; } y = v[i].second; while (a[make_pair(x,y-1)]){ y--, cnt++; int idx = a[make_pair(x,y)]; viz[idx] = 1; what_comp[idx] = nr_nodes; } Size[nr_nodes] = cnt; } } /// construiesc primul arbore 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){ L[x].insert(y); L[y].insert(x); }}} /// verticala memset (viz,0,sizeof viz); for (i=1;i<=n;i++){ if (!viz[i]){ viz[i] = 1; what_comp2[i] = ++nr_nodes2; 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_comp2[idx] = nr_nodes2; } x = v[i].first; while (a[make_pair(x+1,y)]){ x++, cnt++; int idx = a[make_pair(x,y)]; viz[idx] = 1; what_comp2[idx] = nr_nodes2; } Size2[nr_nodes2] = cnt; } } for (i=1;i<=n;i++){ int ic = v[i].first, jc = v[i].second; int x = what_comp2[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_comp2[idx]; if (x != y){ L2[x].insert(y); L2[y].insert(x); }}} dfs (1,0); for (i=1;i<=nr_nodes;i++) sol += 1LL * sum[i] * (n - sum[i]); dfs2 (1,0); for (i=1;i<=nr_nodes2;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...