Submission #395207

#	Time	Username	Problem	Language	Result	Execution time	Memory
395207		Erkhemkhuu	Swapping Cities (APIO20_swap)	C++17	37 / 100	2078 ms	12104 KiB

swap

#include <bits/stdc++.h>
using namespace std;
const int bigN = 100005;
const int lg = 18;
int tin[bigN], tout[bigN];
int depth[bigN], timer, anc[bigN][lg];
int n, m;
int par[bigN], sz[bigN], cnt[bigN];
bool done[bigN];
vector <tuple <int, int, int> > edges;
/*
bool is_ancestor(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int go_up(int v, int u) {
    for(int i = lg - 1; i >= 0; i--)
        if(!is_ancestor(anc[v][i], u))
            v = anc[v][i];
    return v;
}
void dfs(int v, int p) {
    tin[v] = ++timer;
    anc[v][0] = p;
    for(int i = 1; i < lg; i++)
        anc[v][i] = anc[anc[v][i - 1]][i - 1];
    for(auto &u: v) {
        if(u == p) continue;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
    tout[v] = ++timer;
    return;
}
int lca(int v, int u) {
    if(is_ancestor(v, u)) return v;
    if(is_ancestor(u, v)) return u;
    return anc[go_up(v, u)][0];
}
*/
int get(int x) {
    return ((x == par[x]) ? (x) : (par[x] = get(par[x])));
}
void init(int N, int M, vector <int> V, vector <int> U, vector <int> W) {
    n = N; m = M;
    for(int i = 0; i < m; i++)
        edges.push_back({W[i], V[i], U[i]});
    return;
}
void prepare() {
    for(int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
        cnt[i] = 0;
        done[i] = false;
    }
    return;
}
int getMinimumFuelCapacity(int v, int u) {
    prepare();
    sort(edges.begin(), edges.end());
    for(auto &it: edges) {
        int x, y, z;
        tie(z, x, y) = it;
        cnt[x]++; cnt[y]++;

        int X = get(x);
        int Y = get(y);

        bool flag = (X == Y);
        flag |= (cnt[x] >= 3 || cnt[y] >= 3);
        if(flag) done[X] = done[Y] = true;

        if(sz[X] < sz[Y]) swap(X, Y);
        sz[X] += sz[Y];
        done[X] |= done[Y];
        par[Y] = X;

        if(get(v) == get(u) && done[get(v)])
            return z;
    }
    return -1;
}

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