oj.uz

Submission #819854

# Submission time Handle Problem Language Result Execution time Memory
819854 2023-08-10T14:19:07 Z Ahmed57 Ideal city (IOI12_city) C++17
100 / 100
 132 ms 21304 KB 
#include <bits/stdc++.h>

using namespace std;
vector<int> adj[100001];
long long sz[100001];
long long n;
long long all = 0;
long long mod = 1000000000;
void dfs(int i,int pr){
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
        all+=(sz[j]*(n-sz[j]))%mod;
        all%=mod;
        sz[i]+=sz[j];
    }
}
void calc(int *X,int *Y){
    map<pair<int,int>,int> mp,ed;
    vector<pair<int,int>> v;
    for(int i =0;i<n;i++){
        v.push_back({X[i],Y[i]});
    }
    sort(v.begin(),v.end());
    for(int i = 0;i<n;i++){
        mp[{v[i].first,v[i].second}] = i+1;
    }
    int ans[n];int nod = 0;
    for(int i = 0;i<n;i++){
        if(i&&v[i].first==v[i-1].first&&v[i-1].second+1==v[i].second){
            ans[i] = ans[i-1];
        }else {
            adj[nod].clear();
            sz[nod] = 0;
            ans[i] = nod++;
        }
        sz[ans[i]]++;
        int lol = mp[{v[i].first-1,v[i].second}];
        if(lol&&ed[{ans[i],ans[lol-1]}]==0){
            ed[{ans[i],ans[lol-1]}] = 1;
            ed[{ans[lol-1],ans[i]}] = 1;
            adj[ans[i]].push_back(ans[lol-1]);
            adj[ans[lol-1]].push_back(ans[i]);
        }
    }
    dfs(0,-1);
}
int DistanceSum(int N,int *X,int *Y){
    all = 0;
    n = N;
    calc(X,Y);
    calc(Y,X);
    return all;
}
/*int main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<DistanceSum(11,{2,2,3,3,4,4,4,4,5,5,5},{5,6,3,6,3,4,5,6,3,4,6});
}*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 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 2568 KB Output is correct
10 Correct 2 ms 2664 KB Output is correct
11 Correct 1 ms 2664 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2792 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 2 ms 2840 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 2796 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4656 KB Output is correct
2 Correct 18 ms 4660 KB Output is correct
3 Correct 40 ms 7364 KB Output is correct
4 Correct 47 ms 7496 KB Output is correct
5 Correct 89 ms 12092 KB Output is correct
6 Correct 93 ms 12244 KB Output is correct
7 Correct 87 ms 12572 KB Output is correct
8 Correct 85 ms 11912 KB Output is correct
9 Correct 86 ms 12428 KB Output is correct
10 Correct 104 ms 19272 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6464 KB Output is correct
2 Correct 21 ms 5712 KB Output is correct
3 Correct 66 ms 11844 KB Output is correct
4 Correct 51 ms 10172 KB Output is correct
5 Correct 122 ms 21016 KB Output is correct
6 Correct 101 ms 15484 KB Output is correct
7 Correct 132 ms 21304 KB Output is correct
8 Correct 111 ms 15860 KB Output is correct
9 Correct 96 ms 14828 KB Output is correct
10 Correct 99 ms 14400 KB Output is correct