답안 #983556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983556	2024-05-15T17:37:26 Z	RakhimovAmir	자매 도시 (APIO20_swap)	C++17	컴파일 오류	0 ms	0 KB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct edge {
    ll w, x, y;
};

const ll N = 1e5 + 100, M = 30;
vector<pair<ll, ll>> g[N];
vector<edge> edges;
ll prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt;
bool fl[N], visited[N];
vector<ll> v[N];

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

ll findParent(ll x) {
    if (prt[x] == x)
        return x;
    return prt[x] = findParent(prt[x]);
}

void addEdge(ll x, ll y, ll w) {
    g[x].push_back({w, y});
    g[y].push_back({w, x});
}

void merge(ll x, ll y, ll w) {
    ll X = prt[x], Y = prt[y];
    if (X == Y) {
        if (!fl[X])
            return;
        fl[X] = 0;
        for (auto i : v[X]) {
            if (i != X) {
                addEdge(X, i, w);
            }
        }
        return;
    }
    if (v[Y].size() > v[X].size()) {
        swap(x, y);
        swap(X, Y);
    }
    for (auto i : v[Y]) {
        v[X].push_back(i);
    }
    prt[Y] = X;
    if (!fl[X] || !fl[Y] || (x != a[X] && x != b[X]) || (y != a[Y] && y != b[Y])) {
        fl[X] = 0;
        addEdge(X, Y, w);
        return;
    } else {
        if (x == a[X]) {
            if (y == b[Y])
                a[X] = a[Y];
            else
                a[X] = b[Y];
        }
        else {
            if (y == b[Y])
                b[X] = a[Y];
            else
                b[X] = b[Y];
        }
    }
}

void dfs(ll x, ll par, ll w) {
    tin[x] = ++tt;
    visited[x] = 1;
    for (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    p[x][0] = par;
    mx[x][0] = w;
    for (ll i = 1; i < M; i++) {
        p[x][i] = p[p[x][i - 1]][i - 1];
        mx[x][i] = max(mx[x][i - 1], mx[p[x][i - 1]][i - 1]);
        // cout << mx[x][i] << " " << x << " " << i << "\n";
    }
    tout[x] = tt;
}

ll ispr(ll x, ll y) {
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}

ll lca(ll x, ll y) {
    if (ispr(x, y))
        return x;
    if (ispr(y, x))
        return y;
    for (ll i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y))
            x = p[x][i];
    }
    x = p[x][0];
    return x;
}

ll findMax(ll x, ll y) {
    ll ret = 0;
    if (x == y)
        return 0;
     for (ll i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y)) {
            ret = max(ret, mx[x][i]);
            x = p[x][i];
        }
    }
    ret = max(ret, mx[x][0]);
    return ret;
}

void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
    for (ll i = 0; i < N; i++) {
        prt[i] = i;
        a[i] = i;
        b[i] = i;
        fl[i] = 1;
        v[i].push_back(i);
    }
    for (ll i = 0; i < M; i++) {
        edges.push_back({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end(), cmp);
    for (auto i : edges) {
        merge(i.x, i.y, i.w);
    }

    for (ll i = 0; i < N; i++) {
        // ll pr = findParent(i);
        if (!visited[i]) {
            dfs(i, i, 0);
        }
    }
}

ll getMinimumFuelCapacity(ll X, ll Y) {
    ll P = lca(X, Y);
    if (!ispr(P, X) || !ispr(P, Y) || X == Y)
      return -1;
    return max(findMax(X, P), findMax(Y, P));
}

Compilation message

/usr/bin/ld: /tmp/cc0Bd3F9.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