Submission #1190422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190422		Br3ad	Swapping Cities (APIO20_swap)	C++20	30 / 100	314 ms	43528 KiB

swap

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct DSU{
    vector<int> parent, edge_cnt;
    vector<bool> swappable;

    DSU(int n){
        parent = vector<int>(n+1);
        iota(all(parent), 0);

        edge_cnt = vector<int>(n+1, 0);
        swappable = vector<bool>(n+1, false);
    }

    int find_parent(int p){
        return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
    }

    void merge(int a, int b){
        int pa = find_parent(a);
        int pb = find_parent(b);
        edge_cnt[a]++;
        edge_cnt[b]++;

        // Degree >= 3
        if(edge_cnt[a] >= 3) swappable[pa] = true;
        if(edge_cnt[b] >= 3) swappable[pb] = true;

        // Contains cycle
        if(pa == pb) swappable[pb] = true;

        parent[pa] = pb;
        if(swappable[pa]) swappable[pb] = true;
    }

    bool check(int a, int b){
        int pa = find_parent(a);
        int pb = find_parent(b);
        return (pa == pb && swappable[pa]);
    }
};

int _n, _m;
vector<tuple<int, int, int>> edge;

vector<vector<pair<int, int>>> adj(N, vector<pair<int, int>>());
vector<vector<int>> par(N, vector<int>(20)), par_w(N, vector<int>(20, 0));
vector<int> cost(N, inf), tin(N), tout(N);

int timer = 0;
void dfs(int cur, int prev = -1){
    tin[cur] = timer++;
    for(auto [child, w] : adj[cur]){
        if(child == prev) continue;
        par[child][0] = cur;
        par_w[child][0] = w;
        dfs(child, cur);
    }
    tout[cur] = timer++;
}

void cal_cost1(int cur, int prev = -1){
    for(auto [child, w] : adj[cur]){
        if(child == prev) continue;
        cal_cost1(child, cur);
    }

    if((int)adj[cur].size() >= 3){
        int mn1 = inf, mn2 = inf, mn3 = inf;
        for(auto [child, w] : adj[cur]){
            if(w < mn1){
                mn3 = mn2; mn2 = mn1, mn1 = w;
            }else if(w < mn2){
                mn3 = mn2; mn2 = w;
            }else if(w < mn3){
                mn3 = w;
            }
        }
        cost[cur] = mn3;
    }

    for(auto [child, w] : adj[cur]){
        if(child == prev) continue;
        cost[cur] = min(cost[cur], max(cost[child], w));
    }
}

void cal_cost2(int cur, int prev = -1){
    for(auto [child, w] : adj[cur]){
        if(child == prev) continue;
        cost[child] = min(cost[child], max(cost[cur], w));
        cal_cost2(child, cur);
    }
}

bool isAnc(int child, int anc){
    return (tin[anc] <= tin[child] && tout[anc] >= tout[child]);
}

int get_lca(int a, int b){
    if(isAnc(b, a)) return a;
    int lca = b, cur = a;
    for(int i = 19; i >= 0; i--){
        int next_cur = par[cur][i];
        if(isAnc(b, next_cur)){
            lca = next_cur;
        }else {
            cur = next_cur;
        }
    }
    return lca;
}

int get_lca_weight(int a, int lca){
    int cur = a, val = 0;
    for(int i = 19; i >= 0; i--){;
        int next_cur = par[cur][i];
        if(isAnc(next_cur, lca)){
            val = max(val, par_w[cur][i]);
            cur = next_cur;
        }
    }
    return val;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    _n = n;
    _m = m;
    if(m != n-1) return;

    // Subtask 4
    for(int i = 0; i < m; i++) edge.PB({w[i], u[i], v[i]});
    sort(all(edge));

    // Subtask 5
    for(int i = 0; i < m; i++){
        adj[u[i]].PB(MP(v[i], w[i]));
        adj[v[i]].PB(MP(u[i], w[i]));
    }

    par[0][0] = 0;
    par_w[0][0] = 0;
    dfs(0);

    for(int i = 1; i < 20; i++){
        for(int j = 0; j < n; j++){
            par[j][i] = par[par[j][i-1]][i-1];
            par_w[j][i] = max(par_w[j][i-1], par_w[par[j][i-1]][i-1]);
        }
    }
    
    cal_cost1(0);
    cal_cost2(0);
}

// Subtask 3 & 4
int getMinimumFuelCapacity4(int x, int y){
    DSU dsu(_n);
    for(int i = 0; i < _m; i++){
        auto [w, u, v] = edge[i];
        dsu.merge(u, v);
        if(dsu.check(x, y)) return w;
    }
    return -1;
}

// Subtask 5
int getMinimumFuelCapacity(int x, int y){
    int lca = get_lca(x, y);
    int wx = get_lca_weight(x, lca);
    int wy = get_lca_weight(y, lca);

    int ans = max3(cost[x], wx, wy);
    if(ans == inf) ans = -1;

    return ans;
}

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