Submission #810887

#	Time	Username	Problem	Language	Result	Execution time	Memory
810887		Khizri	Ideal city (IOI12_city)	C++17	32 / 100	96 ms	3412 KiB

city

#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);
    }
    ll 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(int i=0;i<n;i++){
        suf-=x[i];
        say--;
        ll res=x[i]*i-pre;
        ll res2=suf-x[i]*say;
        ans=(ans+res)%MOD;
        ans=(ans+res2)%MOD;
        pre+=x[i];
    }
    pre=0,suf=0,say=n;
    for(int i=0;i<n;i++){
        suf+=y[i];
    }
    for(int i=0;i<n;i++){
        suf-=y[i];
        say--;
        ll res=y[i]*i-pre;
        ll res2=suf-y[i]*say;
        ans=(ans+res)%MOD;
        ans=(ans+res2)%MOD;
        pre+=y[i];
    }
    int res=ans;
    return res/2;
}
/*
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++){
      |                 ~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45