Submission #923176

#TimeUsernameProblemLanguageResultExecution timeMemory
923176DzadzoIdeal city (IOI12_city)C++17
Compilation error
0 ms0 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; } signed main() { ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int n; cin>>n; int x[n],y[n]; for (int i=0;i<n;i++)cin>>x[i]>>y[i]; cout<<DistanceSum(n,x,y); }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccnZRSro.o: in function `main':
city.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3mIlcq.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status