Submission #923177

#TimeUsernameProblemLanguageResultExecution timeMemory
923177DzadzoIdeal city (IOI12_city)C++17
100 / 100
159 ms47048 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define S second #define F first #define pii pair<ll,ll> #define vi vector <ll> #define vvi vector <vi> #define vvvi vector <vvi> #define vp vector <pii> #define vvp vector <vp> #define vb vector <bool> #define vvb vector <vb>; #define INF LLONG_MAX #define MOD 1000000000 #define MAXN 1000000 using namespace std; vvi adj(MAXN+1); vi a(MAXN+1); ll ans=0; int n; void dfs(ll v,ll p){ for (int to:adj[v]){ if (to==p)continue; dfs(to,v); a[v]+=a[to]; } ans=(ans+(a[v]*(n-a[v]))%MOD)%MOD; } int DistanceSum(int N, int X[], int Y[]){ n=N; vp arr; map <pii,ll> m; for (ll i=0;i<N;i++)arr.pb({1ll*X[i],1ll*Y[i]}); sort(arr.begin(),arr.end()); ll cnt=0; ll sz=0; for (auto &[x,y]:arr){ if (!m[{x,y-1}]){ a[cnt]=sz; cnt++; sz=1; if (m[{x-1,y}]){ adj[cnt].pb(m[{x-1,y}]); adj[m[{x-1,y}]].pb(cnt); } }else{ sz++; if (m[{x-1,y}] && !m[{x-1,y-1}]){ adj[cnt].pb(m[{x-1,y}]); adj[m[{x-1,y}]].pb(cnt); } } m[{x,y}]=cnt; } a[cnt]=sz; dfs(1,0); arr.clear(); m.clear(); cnt=sz=0; adj.assign(MAXN+1,{}); a.assign(MAXN+1,0); for (ll i=0;i<N;i++)arr.pb({1ll*Y[i],1ll*X[i]}); sort(arr.begin(),arr.end()); for (auto &[y,x]:arr){ if (!m[{x-1,y}]){ a[cnt]=sz; cnt++; sz=1; if (m[{x,y-1}]){ adj[cnt].pb(m[{x,y-1}]); adj[m[{x,y-1}]].pb(cnt); } }else{ sz++; if (m[{x,y-1}] && !m[{x-1,y-1}]){ adj[cnt].pb(m[{x,y-1}]); adj[m[{x,y-1}]].pb(cnt); } } m[{x,y}]=cnt; } a[cnt]=sz; dfs(1,0); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...