oj.uz

Submission #482641

# Submission time Handle Problem Language Result Execution time Memory
482641 2021-10-26T01:39:35 Z Haruto810198 Ideal city (IOI12_city) C++17
32 / 100
 23 ms 5240 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 = 1000000007;
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[v] * (n - dp[v]);
}

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(int N, int *X, int *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();

    return res;

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 1 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 2 ms 2664 KB Output is correct
8 Correct 2 ms 2656 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2656 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 3 ms 2764 KB Output is correct
2 Correct 4 ms 2764 KB Output is correct
3 Correct 3 ms 2788 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 4 ms 2800 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 4 ms 2792 KB Output is correct
10 Correct 3 ms 2792 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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