Submission #979607

#	Time	Username	Problem	Language	Result	Execution time	Memory
979607		vjudge1	Swapping Cities (APIO20_swap)	C++17	0 / 100	2044 ms	26812 KiB

swap

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

using namespace std;
using ll = long long;

const int N = 100100;
const int INF = 1e9 + 10;

struct DSU {
    vector<int> p, r;
    void init(int n) {
        p.assign(n, 0);
        r.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] = (p[x] == x ? x : find(p[x]));
    }
    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (r[u] < r[v]) swap(u, v);
        p[v] = u;
        r[u] += r[v];
    }
};

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

int n, m;
vector<pair<int, int>> G[N];
vector<edge> edges;

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

vector<int> g[N];

vector<bool> vis;
vector<int> par;

void travel(int s) {
    vis[s] = true;
    for (int to : g[s]) if (!vis[to]) {
        par[to] = s;
        travel(to);
    }
}

vector<int> find_path(int x, int y) {
    vis.assign(n, 0);
    par.assign(n, 0);
    travel(x);
    assert(vis[y]);
    vector<int> res;
    while (y != x) {
        res.push_back(y);
        y = par[y];
    }
    res.push_back(x);
    reverse(res.begin(), res.end());
    return res;
}

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 0; i < n; i++) 
        g[i].clear();
    
    int res = -INF, mn = INF;
    DSU ds;
    ds.init(n);

    for (auto [u, v, w] : edges) {
        ds.unite(u, v);
        g[u].push_back(v);
        g[v].push_back(u);
        if (ds.find(X) == ds.find(Y)) {
            res = w;
            break;
        }
    }

    set<pair<int, int>> deleted;

    vector<int> vertices = find_path(X, Y);
    for (int i = 0; i < (int)vertices.size() - 1; i++) {
        deleted.insert({vertices[i], vertices[i + 1]});
        deleted.insert({vertices[i + 1], vertices[i]});
    } 
    
    
    for (int u : vertices) {
        if (u == X || u == Y) continue;;
        for (auto [to, w] : G[u]) 
            if (!deleted.count({u, to})) {
                mn = min(mn, w);
            }
    }


    ds.init(n);

    for (auto [u, v, w] : edges) {
        if (deleted.count({u, v})) continue;
        
        ds.unite(u, v);
        if (ds.find(X) == ds.find(Y)) {
            mn = min(mn, w);
            break;
        }
    }

    if (mn == INF) return -1;
    return max(mn, res); 
}

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