Submission #1018624

#TimeUsernameProblemLanguageResultExecution timeMemory
1018624pccIdeal city (IOI12_city)C++17
0 / 100
108 ms3164 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,sse4") #define pii pair<int,int> #define fs first #define sc second #define ll long long const ll mod = 1e9; const int mxn = 1e5+10; vector<int> paths[mxn]; vector<pii> v; int N; ll mad(ll a,ll b){ assert(a>=0&&b>=0); a %= mod; a += b; return a>=mod?a%mod:a; } ll mub(int a,int b){ assert(a>=0&&b>=0); return mad(a,mod-b%mod); } namespace SUB1{ int dist[mxn]; queue<int> q; int BFS(int now){ memset(dist,-1,sizeof(dist)); dist[now] = 0; q.push(now); while(!q.empty()){ auto now = q.front(); q.pop(); for(auto nxt:paths[now]){ if(dist[nxt] == -1){ dist[nxt] = dist[now]+1; q.push(nxt); } } } int re = 0; for(int i = 0;i<N;i++)re = (re+dist[i])%mod; return re; } int GO(int NN,int* xx,int *yy){ N = NN; for(int i = 0;i<N;i++){ v.push_back(pii(xx[i],yy[i])); } vector<int> perm; for(int i = 0;i<N;i++)perm.push_back(i); sort(perm.begin(),perm.end(),[](int a,int b){return v[a].fs == v[b].fs?v[a].sc<v[b].sc:v[a].fs<v[b].fs;}); for(int i = 1;i<N;i++){ int now = perm[i],pre = perm[i-1]; if(v[now].fs == v[pre].fs&&v[now].sc == v[pre].sc+1){ paths[now].push_back(pre); paths[pre].push_back(now); } } sort(perm.begin(),perm.end(),[](int a,int b){return v[a].sc == v[b].sc?v[a].fs<v[b].fs:v[a].sc<v[b].sc;}); for(int i = 1;i<N;i++){ int now = perm[i],pre = perm[i-1]; if(v[now].sc == v[pre].sc&&v[now].fs == v[pre].fs+1){ paths[now].push_back(pre); paths[pre].push_back(now); } } int ans = 0; for(int i = 0;i<N;i++){ ans += BFS(i); ans %= mod; } assert(ans%2 == 0); return ans>>1; } } namespace SUB2{ int GO(int NN,int *X,int *Y){ N = NN; ll ans = 0; sort(X,X+N);sort(Y,Y+N); for(int i = 0;i<N;i++){ for(int j = 0;j<N;j++){ ans += 1ll*abs(X[i]-X[j])+1ll*abs(Y[i]-Y[j]); } ans %= mod; } return ans>>1; ll suf = 0,pref = 0,cnt = 0; for(int i = 0;i<N;i++)suf += X[i]; for(int i = 0;i<N;i++){ ans += (1ll*X[i]*cnt-pref)+suf-1ll*X[i]*(N-cnt); assert(1ll*X[i]*cnt-pref>=0&&suf-1ll*X[i]*(N-cnt)>=0); ans %= mod; cnt++; pref += X[i]; suf -= X[i]; } suf = pref = cnt = 0; for(int i = 0;i<N;i++)suf += Y[i]; for(int i = 0;i<N;i++){ ans += (1ll*Y[i]*cnt-pref)+suf-1ll*Y[i]*(N-cnt); assert(1ll*Y[i]*cnt-pref>=0&&suf-1ll*Y[i]*(N-cnt)>=0); ans %= mod; cnt++; pref += Y[i]; suf -= Y[i]; } assert(ans%2 == 0); return ans>>1; } } int DistanceSum(int N, int *X, int *Y) { return SUB2::GO(N,X,Y); if(N<=2000)return SUB1::GO(N,X,Y); else return SUB2::GO(N,X,Y); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...