Submission #810896

#TimeUsernameProblemLanguageResultExecution timeMemory
810896KhizriIdeal city (IOI12_city)C++17
55 / 100
92 ms6420 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9) const int mxn=1e5+5; int n; int x[4]={1,-1,0,0}; int y[4]={0,0,1,-1}; vector<pii>vt; vector<int>adj[mxn]; map<pii,int>idx; int solve(){ for(int i=0;i<n;i++){ idx[{vt[i].F,vt[i].S}]=i+1; } for(int i=0;i<n;i++){ int a=vt[i].F,b=vt[i].S; for(int j=0;j<4;j++){ int l=a+x[j],r=b+y[j]; int node=idx[{l,r}]; if(node!=0&&node>i+1){ adj[i+1].pb(node); adj[node].pb(i+1); } } } int ans=0; for(int i=1;i<=n;i++){ vector<int>dis(n+5,-1); dis[i]=0; queue<int>q; q.push(i); while(q.size()){ int u=q.front(); q.pop(); for(int v:adj[u]){ if(dis[v]==-1){ dis[v]=dis[u]+1; q.push(v); } } } for(int j=1;j<=n;j++){ ans=(ans+dis[j])%MOD; } } return ans/2; } int DistanceSum(int N, int *X, int *Y) { n=N; ll l=INF,r=INF; for(int i=0;i<n;i++){ vt.pb({X[i],Y[i]}); l=min(l,1ll*X[i]); r=min(r,1ll*Y[i]); } if(n<=2000){ return solve(); } vector<int>x,y; for(int i=0;i<vt.size();i++){ x.pb(vt[i].F-l+1); y.pb(vt[i].S-r+1); } __int128 ans=0; sort(all(x)); sort(all(y)); ll pre=0,suf=0,say=n; for(int i=0;i<n;i++){ suf+=x[i]; } for(ll i=0;i<n;i++){ suf-=x[i]; say--; ll res=x[i]*i-pre; ll res2=suf-x[i]*say; ans=(ans+res); ans=(ans+res2); pre+=x[i]; } pre=0,suf=0,say=n; for(int i=0;i<n;i++){ suf+=y[i]; } for(ll i=0;i<n;i++){ suf-=y[i]; say--; ll res=y[i]*i-pre; ll res2=suf-y[i]*say; ans=(ans+res); ans=(ans+res2); pre+=y[i]; } ans/=2; ans=(ans%MOD); int res=ans; return res; } /* g++ city.cpp grader.cpp ; .\a.exe */

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<vt.size();i++){
      |                 ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...