oj.uz

Submission #482669

# Submission time Handle Problem Language Result Execution time Memory
482669 2021-10-26T03:09:06 Z Haruto810198 Ideal city (IOI12_city) C++17
100 / 100
 144 ms 18868 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
//const int LNF = INF*INF;
const int MOD = 1000000000;
const int mod = 998244353;
const double eps = 1e-12;

const int MAX = 100010;

int n;
pii pt[MAX];
map<pair<int, int>, int> mp;
int p[MAX], sz[MAX];
int node_p[MAX], w[MAX], dp[MAX];
vi edge[MAX];
int res;

void init(){
    FOR(i, 0, n-1, 1){
        p[i] = i;
        sz[i] = 1;
    }
}

int findp(int v){
    if(v == p[v]) return v;
    return p[v] = findp(p[v]);
}

bool uni(int u, int v){
    int pu = findp(u);
    int pv = findp(v);
    if(pu == pv) return 0;
    if(sz[pu] > sz[pv]){
        p[pv] = pu;
        sz[pu] += sz[pv];
    }
    else{
        p[pu] = pv;
        sz[pv] += sz[pu];
    }
    return 1;
}

void dfs(int v, int pv){
    dp[v] = w[v];
    for(int i : edge[v]){
        if(i == pv) continue;
        dfs(i, v);
        dp[v] += dp[i];
        res += dp[i] * (n - dp[i]);
    }
}

void solve(){

    sort(pt, pt+n);

    mp.clear();
    FOR(i, 0, n-1, 1){
        mp[pt[i]] = i;
    }

    FOR(i, 0, n-1, 1){
        w[i] = 0;
        edge[i].clear();
    }

    init();
    FOR(i, 1, n-1, 1){
        if(pt[i-1].F == pt[i].F and pt[i-1].S == pt[i].S - 1){
            uni(i-1, i);
        }
    }

    FOR(i, 0, n-1, 1){
        node_p[i] = findp(i);
        w[i] = sz[i];
    }

    init();
    FOR(i, 1, n-1, 1){
        if(mp.find(mkp(pt[i].F - 1, pt[i].S)) != mp.end()){
            int u = mp[mkp(pt[i].F - 1, pt[i].S)];
            if(uni(node_p[u], node_p[i])){
                edge[node_p[u]].pb(node_p[i]);
                edge[node_p[i]].pb(node_p[u]);
            }
        }
    }

    dfs(node_p[0], -1);

    return;

}

int DistanceSum(signed N, signed *X, signed *Y){

    n = N;

    FOR(i, 0, n-1, 1){
        pt[i] = mkp(X[i], Y[i]);
    }

    solve();

    FOR(i, 0, n-1, 1){
        pt[i] = mkp(Y[i], X[i]);
    }

    solve();

    //assert(res <= INF);

    res %= MOD;
    return res;

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2668 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2608 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 1 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2724 KB Output is correct
3 Correct 2 ms 2892 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 3 ms 2892 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5232 KB Output is correct
2 Correct 23 ms 5348 KB Output is correct
3 Correct 61 ms 9420 KB Output is correct
4 Correct 57 ms 9436 KB Output is correct
5 Correct 136 ms 16068 KB Output is correct
6 Correct 118 ms 16020 KB Output is correct
7 Correct 121 ms 16276 KB Output is correct
8 Correct 126 ms 15948 KB Output is correct
9 Correct 142 ms 16148 KB Output is correct
10 Correct 117 ms 18868 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5708 KB Output is correct
2 Correct 27 ms 5744 KB Output is correct
3 Correct 65 ms 10436 KB Output is correct
4 Correct 76 ms 10204 KB Output is correct
5 Correct 133 ms 18260 KB Output is correct
6 Correct 128 ms 17092 KB Output is correct
7 Correct 144 ms 18464 KB Output is correct
8 Correct 132 ms 17092 KB Output is correct
9 Correct 126 ms 16672 KB Output is correct
10 Correct 133 ms 16700 KB Output is correct