제출 #1217443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217443		_callmelucian	자매 도시 (APIO20_swap)	C++17	100 / 100	186 ms	54156 KiB

swap

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "swap.h"
#endif // LOCAL
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct DSU {
    vector<int> lab, contain, id;
    int counter;

    DSU (int sz) : lab(sz + 1, -1), contain(sz + 1),
                   id(sz + 1), counter(sz) { iota(all(id), 0); }

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    int getID (int u) { return id[get(u)]; }
    bool good (int u) { return contain[get(u)]; }

    bool unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b)
            return contain[a] = 1, id[a] = ++counter, 0;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        contain[a] |= contain[b], id[a] = ++counter;
        return 1;
    }

    void setNode (int u) { contain[get(u)] = 1; }
};

const int mn = 3e5 + 5;
int up[mn][20], curDeg[mn], depth[mn], weight[mn], n, m;
bool good[mn], vis[mn];
vector<int> adj[mn];
vector<tpl> edges;

void dfs (int u, int p, int d) {
    up[u][0] = p, depth[u] = d;
    for (int i = 1; i < 20; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : adj[u]) dfs(v, u, d + 1);
}

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++)
        edges.emplace_back(W[i], U[i] + 1, V[i] + 1);
    sort(all(edges));

    /// build kruskal reconstruction tree
    DSU dsu(n);
    for (int i = 0; i < m; i++) {
        int a, b, c; tie(c, a, b) = edges[i];
        int u = dsu.getID(a), v = dsu.getID(b);
        if (!u) cout << "troi oi " << a << endl;
        if (!v) cout << "troi oi " << b << endl;

        // mark special nodes
        if (++curDeg[a] == 3) dsu.setNode(a);
        if (++curDeg[b] == 3) dsu.setNode(b);


        // merge component
        bool connected = dsu.unite(a, b);
        int cur = dsu.getID(a);
        adj[cur].push_back(u);
        if (connected)
            adj[cur].push_back(v);

        weight[cur] = c, good[cur] = dsu.good(a);
    }
    weight[0] = -1, good[0] = 1;

//    for (int i = 1; i <= n + m; i++) {
//        cout << "node " << i << ": ";
//        for (int j : adj[i]) cout << j << " ";
//        cout << "\n";
//    }

    /// run dfs
    for (int i = 1; i <= n; i++) {
        int u = dsu.getID(i);
        if (!vis[u]) dfs(u, 0, 0), vis[u] = 1;
    }
}

int goUp (int a, int k) {
    for (int i = 0; k; i++, k >>= 1)
        if (k & 1) a = up[a][i];
    return a;
}

int lca (int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = goUp(a, depth[a] - depth[b]);
    if (a == b && good[a]) return a;
    for (int i = 19; i >= 0; i--)
        if (up[a][i] != up[b][i] || !good[up[a][i]]) a = up[a][i], b = up[b][i];
    return up[a][0];
}

int getMinimumFuelCapacity (int X, int Y) {
    return weight[lca(X + 1, Y + 1)];
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27