Submission #97725

#TimeUsernameProblemLanguageResultExecution timeMemory
97725TAMREFIdeal city (IOI12_city)C++11
23 / 100
166 ms22024 KiB
#include <bits/stdc++.h> #define va first #define vb second #define lb lower_bound #define ub upper_bound #define pb push_back #define emp emplace_back #define all(v) (v).begin(),(v).end() #define szz(v) ((int)(v).size()) #define fio ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; using ll = long long; using lf = long double; using pii = pair<int,int>; using pll = pair<ll,ll>; const int mx = 1e5 + 5; const ll mod = 1e9; pii P[mx]; int n; int rep[mx]; ll sz[mx], dep[mx]; ll ss[mx], sds[mx]; bool vis[mx]; vector<int> G[mx], C[mx]; int f(int x){ return x == rep[x] ? x : rep[x] = f(rep[x]); } void c(int x, int y){ x = f(x); y = f(y); if(x != y){ rep[y] = x; sz[x] += sz[y]; } } unordered_map<ll,int> S; void dfsi(int x){ vis[x] = 1; for(int u : G[x]){ if(vis[u]) continue; C[x].push_back(u); dep[u] = dep[x] + 1; dfsi(u); } } ll dis; void dfs(int x){ ll SS = sz[x], SSQ = sz[x] * sz[x] % mod, SDS = sz[x] * dep[x] % mod, SDSQ = sz[x] * sz[x] * dep[x] % mod; for(int u : C[x]){ dfs(u); SS += ss[u]; SS %= mod; SSQ += ss[u] * ss[u] % mod; SSQ %= mod; SDS += sds[u]; SDS %= mod; SDSQ += sds[u] * ss[u] % mod; SDSQ %= mod; } //printf("dfs on %d : ss = %lld, ssq = %lld, sds = %lld, sdsq = %lld\n",x,ss[x],ssq[x],sds[x],sdsq[x]); dis += SDS * SS % mod - SDSQ - dep[x] * (SS * SS % mod - SSQ) % mod; dis = (dis % mod + mod) % mod; ss[x] = SS; sds[x] = SDS; //printf("dis = %lld\n",dis); } ll pro(){ iota(rep,rep+n,0); fill(sz,sz+n,1); fill(sds,sds+n,0); fill(ss,ss+n,0); fill(dep,dep+n,0); fill(vis,vis+n,0); S.clear(); dis = 0; for(int i = 0; i < n; i++) G[i].clear(), C[i].clear(); sort(P,P+n); int cur = 0; for(int i = 0; i < n; i++) S[ll(P[i].va) << 32 | P[i].vb] = i; for(int i = 1; i < n; i++){ if(P[cur].va != P[i].va){ cur = i; continue; } if(P[i].vb - P[i-1].vb == 1){ c(cur, i); } } for(int i = 0; i < n; i++){ ll V = ll(P[i].va-1) << 32 | P[i].vb; if(S.count(V)){ G[f(S[V])].push_back(f(i)); G[f(i)].push_back(f(S[V])); } } /* for(int i = 0; i < n; i++){ printf("(%d,%d) : %d\n",P[i].va,P[i].vb,f(i)); } */ for(int i = 0; i < n; i++){ if(i != f(i)) continue; sort(all(G[i])); G[i].resize(unique(all(G[i])) - G[i].begin()); //printf("%d, sz = %d: ",i,sz[i]); for(int u : G[i]) printf("%d ",u); puts(""); } dfsi(f(0)); dfs(f(0)); return dis; } int DistanceSum(int N, int *X, int *Y){ n = N; for(int i = 0; i < N; i++) P[i] = {X[i],Y[i]}; ll d1 = pro(); for(int i = 0; i < N; i++) P[i] = {Y[i],X[i]}; ll d2 = pro(); return (d1 + d2) % mod; } /* int main(){ fio; cin >> n; for(int i = 0; i < n; i++) cin >> P[i].va >> P[i].vb; ll d1 = pro(); for(int i = 0; i < n; i++) swap(P[i].va, P[i].vb); ll d2 = pro(); cout << (d1 + d2) % mod << '\n'; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...