Submission #645234

#	Time	Username	Problem	Language	Result	Execution time	Memory
645234		dooompy	Swapping Cities (APIO20_swap)	C++17	100 / 100	365 ms	52256 KiB

swap

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int par[300005];
int cost[300005];

vector<int> adj[300005];
int deg[300005];

int findset(int i) {
    return (par[i] == i ? i : par[i] = findset(par[i]));
}

void onion(int a, int b, int idx) {
    par[a] = idx, par[b] = idx;
    adj[idx].push_back(a);
    adj[idx].push_back(b);
}

int up[300005][20];
int depth[300005];

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    vector<pair<int, pair<int, int>>> edges;

    fill(cost, cost+300005, INT_MAX);
    fill(&up[0][0], &up[0][0] + sizeof(up) / sizeof(up[0][0]), -1);

    for (int i = 1; i < 300005; i++) par[i] = i;

    for (int i = 0; i < M; i++) {
        edges.push_back({W[i], {U[i], V[i]}});
    }

    sort(edges.begin(), edges.end());

    int idx = N;

    for (auto edge : edges) {
        int a = findset(edge.second.first), b = findset(edge.second.second);

        if (a == b) {
            cost[a] = min(cost[a], edge.first);
        } else {
            onion(a, b, ++idx);

            up[a][0] = idx; up[b][0] = idx;

            if (cost[a] != INT_MAX || cost[b] != INT_MAX || deg[edge.second.first] >= 2 || deg[edge.second.second] >= 2) {
                cost[idx] = edge.first;
            }
        }

        deg[edge.second.first]++;
        deg[edge.second.second]++;
    }

    for (int i = idx; i >= 0; i--) {
        for (auto child : adj[i]) {
            depth[child] = depth[i] + 1;
            cost[child] = min(cost[child], cost[i]);
        }
    }



    for (int i = idx; i >= 0; i--) {
        int j = 0;
        while (up[i][j] != -1) {
            up[i][j+1] = up[up[i][j]][j];
            j++;
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if (depth[X] < depth[Y]) swap(X, Y);

    for (int j = 19; j >= 0; j--) {
        if (up[X][j] == -1) continue;
        if (depth[up[X][j]] >= depth[Y]) {
            X = up[X][j];
        }
    }

    while (X != Y) {
        int j = 19;
        while (up[X][j] == up[Y][j] && j > 0) j--;
        X = up[X][j];
        Y = up[Y][j];
    }

    return cost[X] == INT_MAX ? -1 : cost[X];
}

//int main() {
//	int N, M;
//	cin >> N >> M;
//	vector<int> U(M), V(M), W(M);
//	for (int i = 0; i < M; i++)cin >> U[i] >> V[i] >> W[i];
//	init(N, M, U, V, W);
//	int Q;
//	cin >> Q;
//	while (Q--) {
//		int a, b;
//		cin >> a >> b;
//		cout << getMinimumFuelCapacity(a, b) << "\n";
//	}
//}

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