Submission #982531

#	Time	Username	Problem	Language	Result	Execution time	Memory
982531		vjudge1	Swapping Cities (APIO20_swap)	C++17	100 / 100	253 ms	53360 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"

using namespace std;
using ll = long long;

const int N = 300300;

const int INF = 1e9;

struct edge {
    int u;
    int v;
    int w;
};  

int bg[N];
int en[N];
int cap[N];
bool isbam[N];
int head[N];
int par[N][18];


vector<edge> edges;

int find(int x) {
    return head[x] = (head[x] == x ? x : find(head[x]));
};

vector<int> g[N];
int tin[N], tout[N], T;

void dfs(int s) {
    tin[s] = ++T;
    for (int to : g[s]) {
        dfs(to);
    }
    tout[s] = T;
}

bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++) {
        edges.push_back({U[i], V[i], W[i]});
    }
    
    sort(edges.begin(), edges.end(), [](edge x, edge y) {
        return x.w < y.w;
    });

    int lst = N - 1;
    for (int i = 0; i < N; i++) {
        bg[i] = en[i] = i;
        head[i] = i;
        isbam[i] = true;
    }
    for (auto e : edges) {
        lst++;
        int t1 = find(e.u);
        int t2 = find(e.v);

        head[lst] = par[lst][0] = lst;
        par[t1][0] = par[t2][0] = lst;
        head[t1] = head[t2] = lst;
        cap[lst] = e.w;

        if (t1 == t2) {
            bg[lst] = bg[t1];
            en[lst] = en[t1];
            isbam[lst] = false;
        } else {
            int ar[2][2] = {{bg[t1], en[t1]}, {bg[t2], en[t2]}}; 
            
            bool flag = true; 
            for (int bit_0 = 0; bit_0 < 2 && flag; bit_0++) {
                for (int bit_1 = 0; bit_1 < 2; bit_1++) {
                    if (e.u == ar[0][bit_0] && e.v == ar[1][bit_1]) {
                        bg[lst] = ar[0][!bit_0];
                        en[lst] = ar[1][!bit_1];
                        flag = false;
                        break;
                    }
                    if (e.v == ar[0][bit_0] && e.u == ar[1][bit_1]) {
                        bg[lst] = ar[0][!bit_0];
                        en[lst] = ar[1][!bit_1];
                        flag = false;
                        break;
                    }
                } 
            }
            if (flag) 
                isbam[lst] = false;
            else 
                isbam[lst] = (isbam[t1] & isbam[t2]);
        }
    }
    par[lst][0] = lst;
    for (int i = lst; i >= 0; i--) {
        for (int k = 1; k < 18; k++) {
            par[i][k] = par[ par[i][k - 1] ][k - 1];
        }
        if (par[i][0] != i)
            g[par[i][0]].push_back(i);
    }

    dfs(lst);
}

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 17; i >= 0; i--) {
        if (!up(par[X][i], Y) || isbam[par[X][i]])
            X = par[X][i];
    }
    if (up(par[X][0], Y) && !isbam[par[X][0]]) {
        X = par[X][0];
        return cap[X];
    }
    return -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