oj.uz

Submission #987727

# Submission time Handle Problem Language Result Execution time Memory
987727 2024-05-23T12:55:06 Z vjudge1 Ideal city (IOI12_city) C++17
100 / 100
 175 ms 27592 KB 
#pragma once
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 2e5 + 5;
const int mod = 1e9;
using namespace std;
vector<vector<int>>v;
ll dpD[mxN],dpU[mxN];
ll subD[mxN],subU[mxN];
ll w[mxN];
int p[mxN];
ll ans;
int _N;
void dfs(int u,int par){
	subD[u] = w[u];
    p[u] = par;
	for(auto x : v[u]){
		if(x == par) continue;
		dfs(x,u);
		subD[u] += subD[x];
	}
dpD[u] = (long long) subD[u] * (_N - subD[u]);
}

ll solve(int N,int X[],int Y[]){
    ans = 0;
    for(int i = 0; i <= N;i++){
        dpD[i] = 0;
        dpU[i] = 0;
        subD[i] = 0;
        subU[i] = 0;
        w[i] = 0;
        p[i] = 0;
    }
    map<pii,int>mp;
    map<pii,bool>vis;
    for(auto &x : v) x.clear();
    v.clear();
    v.resize(N + 1);
    int id = 0;
    vector<pii>a;
    for(int i = 0;i < N;i++){
        a.push_back({X[i],Y[i]});
    }
    sort(a.begin(),a.end());
    int pX = -1,pY = -1;
    for(auto x : a){
        if(x.F != pX || x.S != pY + 1){
            id++;
        }
        mp[x] = id;
        w[id]++;
        if(mp[{x.F - 1,x.S}] && !vis[{mp[x],mp[{x.F - 1,x.S}]}]){
            v[mp[{x.F - 1,x.S}]].push_back(mp[x]);
            v[mp[x]].push_back(mp[{x.F - 1,x.S}]);
            vis[{mp[x],mp[{x.F - 1,x.S}]}] = 1;
        }
        pX = x.F;
        pY = x.S;
    }
    // for(int i = 1;i < 7;i++){
    //     cout<<i<<' '<<w[i]<<"{ ";
    //     for(auto x : v[i]){
    //         cout<<x<<' ';
    //     }
    //     cout<<"}\n";
    // }
    dfs(1,0);
    for(int i = 1;i <= N;i++){
        ans += dpD[i] ;
        // cout<<dpD[i]<<' ';
    }
    // cout<<'\n';
    // for(int i = 1;i <= N;i++){
    //     cout<<dpU[i]<<' ';
    // }
    // cout<<'\n';
    // cout<<'\n';
    // ans /= 2;
    // ans %= mod;
    return ans;
}
int DistanceSum(int N, int X[], int Y[]){
     _N = N;
    return (((solve(N,Y,X) + solve(N,X,Y))) % mod);
}

Compilation message

city.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8644 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 2 ms 8648 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 3 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8552 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8796 KB Output is correct
2 Correct 4 ms 8796 KB Output is correct
3 Correct 4 ms 8796 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 5 ms 8796 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 4 ms 9052 KB Output is correct
8 Correct 4 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11088 KB Output is correct
2 Correct 19 ms 11168 KB Output is correct
3 Correct 48 ms 15076 KB Output is correct
4 Correct 47 ms 15036 KB Output is correct
5 Correct 107 ms 21160 KB Output is correct
6 Correct 98 ms 21156 KB Output is correct
7 Correct 98 ms 21412 KB Output is correct
8 Correct 98 ms 20904 KB Output is correct
9 Correct 97 ms 20900 KB Output is correct
10 Correct 123 ms 26480 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12296 KB Output is correct
2 Correct 27 ms 11988 KB Output is correct
3 Correct 81 ms 17884 KB Output is correct
4 Correct 64 ms 16984 KB Output is correct
5 Correct 175 ms 27300 KB Output is correct
6 Correct 134 ms 23720 KB Output is correct
7 Correct 161 ms 27592 KB Output is correct
8 Correct 142 ms 23616 KB Output is correct
9 Correct 130 ms 22832 KB Output is correct
10 Correct 120 ms 22696 KB Output is correct