Submission #341242

#	Time	Username	Problem	Language	Result	Execution time	Memory
341242		phathnv	Swapping Cities (APIO20_swap)	C++11	100 / 100	450 ms	42992 KiB

swap

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

#define X first
#define Y second
#define mp make_pair

using namespace std;

typedef pair<int, int> ii;

const int maxN = 100000;
const int maxM = 200000;

bool vst[maxN];
vector <ii> adj[maxN];
vector <int> adjEdge[maxN];
int nEdge = 0;

void buildEdge(int u, int w){
    for(int v : adjEdge[u])
        if (!vst[v]){
            adj[u].push_back(mp(v, w));
            adj[v].push_back(mp(u, w));
            vst[v] = 1;
            nEdge++;
            buildEdge(v, w);
        }
}

struct DSU{
    int rnk[maxN], root[maxN], deg[maxN];
    int cnt[maxN][4];
    bool ok[maxN];

    void reset(int n){
        for(int i = 0; i < n; i++){
            root[i] = i;
            deg[i] = rnk[i] = 0;
            cnt[i][0] = 1;
            cnt[i][1] = cnt[i][2] = cnt[i][3] = 0;
            ok[i] = 0;
        }
    }
    int getRoot(int u){
        if (u == root[u])
            return u;
        root[u] = getRoot(root[u]);
        return root[u];
    }
    void updateDeg(int u){
        int ru = getRoot(u);
        cnt[ru][deg[u]]--;
        deg[u]++;
        cnt[ru][deg[u]]++;
    }
    bool check(int u){
        u = getRoot(u);
        if (cnt[u][3] > 0 || cnt[u][0] + cnt[u][1] == 0)
            return 1;
        return 0;
    }
    void addEdge(int u, int v, int w){
        if (deg[u] < 3)
            updateDeg(u);
        if (deg[v] < 3)
            updateDeg(v);
        u = getRoot(u);
        v = getRoot(v);
        if (u != v){
            if (rnk[u] > rnk[v])
                swap(u, v);
            if (rnk[u] == rnk[v])
                rnk[u]++;
            root[v] = u;
            adjEdge[u].push_back(v);

            for(int i = 0; i < 4; i++)
                cnt[u][i] += cnt[v][i];
            ok[u] = ok[u] || ok[v];
        }
        ok[u] = ok[u] || check(u);
        if (ok[u])
            buildEdge(u, w);
    }
} G;

int dist[maxN][17], par[maxN][17], h[maxN];

void dfs(int u, int p){
    for(int i = 1; i <= 16; i++){
        par[u][i] = par[par[u][i - 1]][i - 1];
        dist[u][i] = max(dist[u][i - 1], dist[par[u][i - 1]][i - 1]);
    }
    for(ii e : adj[u])
        if (e.X != p){
            par[e.X][0] = u;
            dist[e.X][0] = e.Y;
            h[e.X] = h[u] + 1;
            dfs(e.X, u);
        }
}

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

int n, m;
edge edges[maxM];

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;
    for(int i = 0; i < m; i++){
        edges[i].u = U[i];
        edges[i].v = V[i];
        edges[i].w = W[i];
    }
    sort(edges, edges + m, [](edge &a, edge & b){
            return a.w < b.w;
         });
    G.reset(n);
    for(int i = 0; i < m; i++)
        G.addEdge(edges[i].u, edges[i].v, edges[i].w);
    dfs(0, -1);
}

int getDist(int u, int v){
    int res = 0;
    if (h[u] > h[v])
        swap(u, v);
    for(int i = 16; i >= 0; i--)
        if (h[u] <= h[v] - (1 << i)){
            res = max(res, dist[v][i]);
            v = par[v][i];
        }
    if (v == u)
        return res;
    for(int i = 16; i >= 0; i--)
        if (par[u][i] != par[v][i]){
            res = max(res, dist[u][i]);
            res = max(res, dist[v][i]);
            u = par[u][i];
            v = par[v][i];
        }
    res = max(res, dist[u][0]);
    res = max(res, dist[v][0]);
    return res;
}

int getMinimumFuelCapacity(int X, int Y) {
    if (nEdge == 0)
        return -1;
    return getDist(X, Y);
}

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