Submission #928337

#	Time	Username	Problem	Language	Result	Execution time	Memory
928337		VinhLuu	Swapping Cities (APIO20_swap)	C++17	7 / 100	242 ms	44104 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), tmp = u;
    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];
        }
    }
    u = tmp;
    for(int i = 20; i >= 0; i --){
        if(!kt(dp[v][i], u) || dp[v][i] == k){
            ret = max(ret, mx[v][i]);
            v = dp[v][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;
//    cerr << 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 ++){
        if(p[i].u == p[i].v) continue;
        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]++;
//        cerr << 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);
//    cerr << root << " g\n";
    dfs(root, 0, 0);
}

int getMinimumFuelCapacity(int x,int y){
    x++;
    y++;
//    cerr << x << " " << y << " " << get(x, y) << "f\n";
    int t = lca(x, y), kq = max(f[t], get(x, y));
    return (kq < 1e9 ? kq : -1);
}

//#define LOCAL

#ifdef 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);
    }

    cin >> n >> m;
    vector<int> u, v, w;
    for(int i = 1; i <= m; i ++){
        int x, y, t; cin >> x >> y >> t;
        u.pb(x - 1);
        v.pb(y - 1);
        w.pb(t);
    }
    init(n, m, u, v, w);
    int rq = 0;
    cin >> rq;
//    cerr << rq << "fifai\n";
    while(rq--){
        int x, y;
        cin >> x >> y;
//        cerr << x << " " << y << " rr\n";
        x--;
        y--;

        cout << getMinimumFuelCapacity(x, y) << "\n";
    }
}
#endif // LOCAL

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