답안 #894741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894741	2023-12-28T20:34:10 Z	ShaShi	자매 도시 (APIO20_swap)	C++17	컴파일 오류	0 ms	0 KB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define pb push_back
#define mp make_pair
#define pii pair<int, int>


using namespace std;
typedef long long ll;
typedef long double ld;


const int MAXN = (int)1e6 + 7;
const int LG = 18;
const int MOD = 998244353;
const int INF = (int)1e18 + 7;



int n, m, t, flag, k, u, v, w, ans, ans2, tmp, tmp2, tmp3, tmp4, q, timer;
int arr[MAXN], num[MAXN];
int par[MAXN], love[MAXN], dp[MAXN], deg[MAXN];
int h[MAXN], dad[MAXN], pow2dad[MAXN][LG];
vector<pair<int, pii> > edge;
vector<int> adj[MAXN];


/* DSU */

inline int get_par(int v) {
    return (par[v] == v? v : par[v] = get_par(par[v]));
}


void unite(int u, int v, int w) {
    int u2, v2;
    u2 = u;
    v2 = v;

    deg[u2]++, deg[v2]++;

    u = get_par(u), v = get_par(v);

    if (u == v) {
        if (!love[u]) {
            love[u] = 1;
            num[u] = w;
        }
    } else {
        par[u] = par[v] = flag;
        par[flag] = flag;
        adj[flag].pb(u), adj[flag].pb(v);
        num[flag] = w;

        if (love[u] || love[v]) {
            love[flag] = 1;
        } else {
            love[flag] = (deg[u2] == 3 || deg[v2] == 3);
        }

        // cout << "@" << flag << " " << u << " " << v << endl;

        flag++;
    }

}

/* DSU */

/* LCA */

inline int up(int v, int k) {
    for (int i=LG-1; i>=0; i--) {
        if ((1<<i) <= k) {
            k -= (1<<i);
            v = pow2dad[v][i];
        }
    }

    return v;
}


int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);

    u = up(u, h[u]-h[v]);

    for (int i=LG-1; i>=0; i--) {
        if (h[v] >= (1<<i) && pow2dad[v][i] != pow2dad[u][i]) {
            v = pow2dad[v][i];
            u = pow2dad[u][i];
        }
    }

    if (u == v) return u;
    return dad[v];
}


/* LCA */


void DFS(int v) {
    dp[v] = (love[v]? v : dp[dad[v]]);

    for (int u:adj[v]) {
        if (u != dad[v]) {
            dad[u] = v;
            h[u] = h[v]+1;
            DFS(u);
        }
    }
}


void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;

	for (int i=0; i<m; i++) {
		u = U[i];
		v = V[i];
		w = W[i];

        edge.pb(mp(w, mp(u, v)));
    }

    sort(all(edge));
    flag = n+1;

    for (int i=1; i<=n; i++) par[i] = i;
    
    for (int i=0; i<m; i++) unite(edge[i].S.F, edge[i].S.S, edge[i].F);
    flag--;

    DFS(flag);

    for (int i=1; i<=flag; i++) pow2dad[i][0] = dad[i];
    for (int j=1; j<LG; j++) for (int i=1; i<=flag; i++) pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];
    num[0]--;
}

int getMinimumFuelCapacity(int X, int Y) {
	return num[dp[LCA(X, Y)]];
}

Compilation message

/usr/bin/ld: /tmp/ccF3FwIU.o: in function `main':
grader.cpp:(.text.startup+0x1c3): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x217): undefined reference to `getMinimumFuelCapacity(int, int)'
collect2: error: ld returned 1 exit status