Submission #828138

#	Time	Username	Problem	Language	Result	Execution time	Memory
828138		SUNWOOOOOOOO	Swapping Cities (APIO20_swap)	C++17	37 / 100	2070 ms	11220 KiB

swap

// #include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using tint = array <int, 3>;
const int mxN = 200005;
int n, m, deg[mxN];
tint edge[mxN];

struct dsu {
    tint G[mxN]; // node, is cycle, is deg3
    void init(){
        for (int i = 0; i < n; i++) G[i] = {i, 0, 0};
    }
    int find(int x){
        if (G[x][0] != x) G[x][0] = find(G[x][0]);
        return G[x][0];
    }
    void uni(int x, int y){
        x = find(x), y = find(y);
        if (x != y){
            G[y][0] = x;
            G[x][1] += G[y][1];
            G[x][2] += G[y][2];
        }
        else {
            G[x][1] = 1;
        }
    }
} dsu;

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++) edge[i] = {W[i], U[i], V[i]};
    sort(edge, edge + m);
}

int getMinimumFuelCapacity(int X, int Y) {
    dsu.init();
    memset(deg, 0, sizeof deg);

    for (int i = 0; i < m; i++){
        if (++deg[edge[i][1]] >= 3) dsu.G[dsu.find(edge[i][1])][2] = 1;
        if (++deg[edge[i][2]] >= 3) dsu.G[dsu.find(edge[i][2])][2] = 1;
        dsu.uni(edge[i][1], edge[i][2]);

        X = dsu.find(X), Y = dsu.find(Y);
        if (X == Y && (dsu.G[X][1] || dsu.G[X][2])){
            return edge[i][0];
        }
    }
    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