oj.uz

Submission #810887

# Submission time Handle Problem Language Result Execution time Memory
810887 2023-08-06T17:09:55 Z Khizri Ideal city (IOI12_city) C++17
32 / 100
 96 ms 3412 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2552 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2660 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2656 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2628 KB Output is correct
10 Correct 2 ms 2656 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2840 KB Output is correct
2 Correct 22 ms 2772 KB Output is correct
3 Correct 46 ms 2912 KB Output is correct
4 Correct 50 ms 2876 KB Output is correct
5 Correct 82 ms 2996 KB Output is correct
6 Correct 89 ms 2940 KB Output is correct
7 Correct 86 ms 3028 KB Output is correct
8 Correct 96 ms 2940 KB Output is correct
9 Correct 91 ms 2920 KB Output is correct
10 Correct 86 ms 2900 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3412 KB Output is correct
2 Incorrect 6 ms 3408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -