Submission #928319

#	Time	Username	Problem	Language	Result	Execution time	Memory
928319		VinhLuu	Swapping Cities (APIO20_swap)	C++17	0 / 100	179 ms	43688 KiB

swap

#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
//const int oo = -2e9;
//const int mod = 1e9 + 7;

struct e{
    int u, v, w;
} p[N];

bool comp(e g1, e g2){
    return g1.w < g2.w;
}

int n, m, in[N], out[N], dp[N][22], mx[N][22], demin, demout, root, pa[N], sz[N], f[N], deg[N], re[N];
vector<pii> g[N];

int fin(int u){
    return pa[u] == u ? u : fin(pa[u]);
}

void dfs(int u,int v,int ts){
    in[u] = ++demin;
    if(u == root) for(int i = 0; i <= 20; i ++) dp[u][i] = u;
    else{
        dp[u][0] = v;
        mx[u][0] = ts;
        for(int i = 1; i <= 20; i ++){
            dp[u][i] = dp[dp[u][i - 1]][i - 1];
            mx[u][i] = max(mx[u][i - 1], mx[dp[u][i - 1]][i - 1]);
        }
    }
    for(auto jj : g[u]){
        int j = jj.fi;
        int w = jj.se;
        f[j] = min(f[j], max(f[u], w));
        dfs(j, u, w);
    }
    out[u] = ++demout;
}

bool kt(int u,int v){
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u,int v){
    if(kt(u, v)) return u;
    else{
        int kq = u;
        for(int i = 20; i >= 0; i --){
            if(kt(dp[u][i], v)) kq = dp[u][i];
            else u = dp[u][i];
        }
        return kq;
    }
}

int get(int u,int v){
    int ret = 0, k = lca(u, v);
    for(int i = 20; i >= 0; i --){
        if(!kt(dp[u][i], v) || dp[u][i] == k){
            ret = max(ret, mx[u][i]);
            u = dp[u][i];
        }
    }
    return ret;
}


void dsu(int x,int y,int w){
    x = fin(x);
    y = fin(y);
    if(x == y){
        f[x] = min(f[x], w);
//        cout << x << " " << w << " " << f[x] << " " << re[x] << " change\n";
        return;
    }
    if(sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    pa[y] = x;
//    cout << x << " " << y << " " << w << " f\n";
    g[x].push_back({y, w});
    f[x] = min(f[x], f[y]);
//    re[x] = max({re[x], re[y], w});
}

void init(int N,int M, vector<int> U, vector<int> V, vector<int> W){
    n = N;
    m = M;
    for(int i = 1; i <= n; i ++){
        f[i] = 1e9;
        pa[i] = i;
        sz[i] = 1;
        re[i] = 0;
    }

    for(int i = 0; i < m; i ++){
        p[i + 1].u = U[i] + 1;
        p[i + 1].v = V[i] + 1;
        p[i + 1].w = W[i];
    }
    sort(p + 1, p + m + 1, comp);
    for(int i = 1; i <= m; i ++){
        dsu(p[i].u, p[i].v, p[i].w);
        int u = p[i].u, v = p[i].v, w = p[i].w;
        deg[u]++;
        deg[v]++;
//        cout << u << " " << v << " " << w << " gggg\n";
        int j = fin(u);
        deg[j] = max({deg[j], deg[u], deg[v]});
        if(deg[j] >= 3) f[j] = min(f[j], w);
    }

    root = fin(1);
//    cout << root << " g\n";
    dfs(root, 0, 0);
}

int getMinimumFuelCapacity(int x,int y){
    x++;
    y++;

    int t = lca(x, y), kq = max(f[t], get(x, y));
    return (kq < 1e9 ? kq : -1);
}

//#define LOCAL

#ifdef LOCAL
int main() {
//    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
//    if (fopen ("task.inp", "r")) {
//        freopen ("task.inp", "r", stdin);
//        freopen ("task.out", "w", stdout);
//    }
//    if (fopen (task".inp", "r")) {
//        freopen (task".inp", "r", stdin);
//        freopen (task".out", "w", stdout);
//    }

//    vector<int> u = {0, 0};
//    vector<int> v = {1, 2};
//    vector<int> w = {5, 5};
//    init(3, 2, u, v, w);
//    cout << getMinimumFuelCapacity(1, 2);

    vector<int> u = {0,0,1,1,1,2};
    vector<int> v = {1,2,2,3,4,3};
    vector<int> w = {4,4,1,2,10,3};
    init(5, 6, u, v, w);
    cout << getMinimumFuelCapacity(0, 1);
}
#endif // LOCAL

//signed main(){
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//    #define task "v"
//    if(fopen(task ".inp","r")){
//        freopen(task ".inp","r",stdin);
//        freopen(task ".out","w",stdout);
//    }
//
//
//}

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