Submission #237713

#TimeUsernameProblemLanguageResultExecution timeMemory
237713nicolaalexandraIdeal city (IOI12_city)C++14
32 / 100
1093 ms14840 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],dist[DIM],viz[DIM]; int nr_nodes, nr_nodes2; int di[] = {-1,1,0,0}; int dj[] = {0,0,-1,1}; int bfs (int start){ int i; for (i=1;i<=nr_nodes;i++) dist[i] = INF; c.clear(); c.push_back(start); dist[start] = 0; int sol = 0; while (!c.empty()){ int nod = c.front(); c.pop_front(); for (auto vecin : L[nod]){ if (dist[vecin] == INF){ dist[vecin] = 1 + dist[nod]; sol += 1LL * dist[vecin] * Size[vecin] % MOD; c.push_back(vecin); }}} return sol; } int bfs2 (int start){ int i; for (i=1;i<=nr_nodes2;i++) dist[i] = INF; c.clear(); c.push_back(start); dist[start] = 0; int sol = 0; while (!c.empty()){ int nod = c.front(); c.pop_front(); for (auto vecin : L2[nod]){ if (dist[vecin] == INF){ dist[vecin] = 1 + dist[nod]; sol += 1LL * dist[vecin] * Size2[vecin] % MOD; c.push_back(vecin); }}} return sol; } int DistanceSum (int n, int *X, int *Y){ int i, 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); }}} /// stiu ca o sa iau tle for (i=1;i<=nr_nodes;i++) sol = (sol + 1LL * Size[i] * bfs(i) % MOD) % MOD; for (i=1;i<=nr_nodes2;i++) sol = (sol + 1LL * Size2[i] * bfs2(i) % MOD) % MOD; return sol / 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...