Submission #482668

#	Time	Username	Problem	Language	Result	Execution time	Memory
482668		Haruto810198	Ideal city (IOI12_city)	C++17	32 / 100	28 ms	11384 KiB

city

#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[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);
    return res;

}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45