oj.uz

Submission #810896

# Submission time Handle Problem Language Result Execution time Memory
810896 2023-08-06T17:14:31 Z Khizri Ideal city (IOI12_city) C++17
55 / 100
 92 ms 6420 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);
    }
    __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

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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2772 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 2644 KB Output is correct
10 Correct 2 ms 2644 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 2820 KB Output is correct
2 Correct 21 ms 2772 KB Output is correct
3 Correct 46 ms 2900 KB Output is correct
4 Correct 50 ms 2772 KB Output is correct
5 Correct 81 ms 2988 KB Output is correct
6 Correct 89 ms 2916 KB Output is correct
7 Correct 87 ms 2996 KB Output is correct
8 Correct 92 ms 2924 KB Output is correct
9 Correct 90 ms 2908 KB Output is correct
10 Correct 84 ms 2900 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3280 KB Output is correct
2 Correct 5 ms 3280 KB Output is correct
3 Correct 12 ms 4564 KB Output is correct
4 Correct 12 ms 4564 KB Output is correct
5 Correct 27 ms 6400 KB Output is correct
6 Correct 24 ms 6240 KB Output is correct
7 Correct 25 ms 6420 KB Output is correct
8 Correct 23 ms 6176 KB Output is correct
9 Correct 23 ms 6228 KB Output is correct
10 Correct 23 ms 6228 KB Output is correct

Subtask #4
0 / 45.0

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