Submission #562594

#TimeUsernameProblemLanguageResultExecution timeMemory
562594Leo121Ideal city (IOI12_city)C++14
55 / 100
136 ms5908 KiB
#include <bits/stdc++.h> #define forn(i, a, b) for(int i = int (a); i <= int(b); ++ i) #define fora(i, a, b) for(int i = int (a); i >= int(b); -- i) #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef vector<int> vi; const int maxn = 1e5; int distancia[maxn]; vi graph[maxn]; ll mod = 1e9; ll res = 0; int mx[4] = {0, 0, 1, -1}; int my[4] = {1, -1, 0, 0}; map<pii, int> mapa; queue<int> q; map<int, int> x; map<int, int> y; ll arrex[maxn + 2]; ll arrey[maxn + 2]; void bfs(int ind){ int u; while(!q.empty()){ u = q.front(); q.pop(); for(auto v : graph[u]){ if(distancia[v] == -1){ distancia[v] = distancia[u] + 1; if(v > ind){ res += (ll) distancia[v]; res %= mod; } q.push(v); } } } } int DistanceSum(int N, int *X, int *Y) { if(N <= 2000){ forn(i, 0, N - 1){ mapa[mp(X[i], Y[i])] = i; } forn(i, 0, N - 1){ forn(j, 0, 3){ if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){ graph[i].pb(mapa[mp(X[i] + mx[j], Y[i] + my[j])]); } } } forn(i, 0, N - 1){ memset(distancia, -1, sizeof(distancia)); distancia[i] = 0; q.push(i); bfs(i); } } else{ forn(i, 0, N - 1){ x[X[i]] ++; y[Y[i]] ++; } int longx = 0, longy = 0; for(auto i : x){ arrex[++ longx] = (ll) i.se; } for(auto i : y){ arrey[++ longy] = (ll) i.se; } ll suma = 0; forn(i, 2, longx){ suma += arrex[i] * ((ll) i - 1LL); } res = suma * arrex[1]; res %= mod; fora(i, longx - 1, 2){ arrex[i] += arrex[i + 1]; } forn(i, 2, longx){ suma -= arrex[i]; res += suma * (arrex[i] - arrex[i + 1]); res %= mod; } suma = 0; forn(i, 2, longy){ suma += arrey[i] * ((ll) i - 1LL); } res += suma * arrey[1]; res %= mod; fora(i, longy - 1, 2){ arrey[i] += arrey[i + 1]; } forn(i, 2, longy){ suma -= arrey[i]; res += suma * (arrey[i] - arrey[i + 1]); res %= mod; } } return (int) res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...