답안 #482642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482642	2021-10-26T01:40:16 Z	Haruto810198	이상적인 도시 (IOI12_city)	C++17	컴파일 오류	0 ms	0 KB

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[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;

}

Compilation message

/usr/bin/ld: /tmp/ccXj7VZV.o: in function `main':
grader.cpp:(.text.startup+0x104): undefined reference to `DistanceSum(int, int*, int*)'
collect2: error: ld returned 1 exit status