Submission #1047167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047167		KasymK	Swapping Cities (APIO20_swap)	C++17	53 / 100	123 ms	42820 KiB

swap

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second	
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int maxn = 2e5+5;
const int LOG = 20;
int rep[maxn], C[maxn], deg[maxn], dp[maxn], P[maxn], ok[maxn], G[maxn], d[maxn], n, m, N, up[maxn][LOG];
vector<int> adj[maxn];
vector<array<int, 3>> A;

int find(int x){
    if(x == rep[x])
        return x;
    return rep[x] = find(rep[x]); // path compression
}
 
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    n++;
    if(a == b)
        C[n] = 1;
    rep[n] = rep[a] = rep[b] = n;
    if(G[a] or G[b])
        G[n] = 1;
    if(C[a] or C[b])
        C[n] = 1;
    adj[n].pb(a);
    if(a != b) adj[n].pb(b);
}
 
void dfs(int x, int pr = -1) {
    for(int i = 1; i < LOG; ++i){
        if(~up[x][i-1])
            up[x][i] = up[up[x][i-1]][i-1];
        else
            up[x][i] = -1;
    }
    if(ok[x])
        pr = x;
    dp[x] = pr;
    for(int &i : adj[x]) {
        d[i] = d[x]+1;
        up[i][0] = x;
        P[i] = x;
        dfs(i, pr);
    }
}

int LCA(int a, int b) {
    if(d[a] < d[b])
        swap(a, b);
    int diff = d[a]-d[b];
    for(int i = LOG-1; i >= 0; --i)
        if(diff>>i&1)
            a = up[a][i];
    if(a == b)
        return a;
    for(int i = LOG-1; i >= 0; --i)
        if(up[a][i] != up[b][i])
            a = up[a][i], b = up[b][i];
    return up[a][0];
}
 
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    n = _N; N = _N; m = _M;
    for(int i = 1; i <= n+m; ++i)
        rep[i] = i;
    for(int i = 0; i < m; ++i)
        A.pb({W[i], U[i]+1, V[i]+1});
    sort(all(A));
    for(auto &[w, u, v] : A){
        deg[u]++, deg[v]++;
        if(deg[u] >= 3 or deg[v] >= 3)
            G[n+1] = 1;
        merge(u, v);
    }
    for(int i = 1; i <= n; ++i)
        ok[i] = (G[i] or C[i]);
    dfs(n);
}
 
int getMinimumFuelCapacity(int x, int y) {
    x++, y++;
    int ad = LCA(x, y);
    if(dp[ad] == -1)
        return -1;
    return A[dp[ad]-N-1][0];
}

// int main(){
//     init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
//     vector<int> Sol;
//     Sol.pb(3);
//     Sol.pb(10);
//     Sol.pb(4);
//     vector<int> equal;
//     int rt = getMinimumFuelCapacity(1, 2);
//     equal.pb(rt);
//     rt = getMinimumFuelCapacity(2, 4);
//     equal.pb(rt);
//     rt = getMinimumFuelCapacity(0, 1);
//     equal.pb(rt);
//     if(equal == Sol)
//         puts("Correct.");
//     else{
//         for(int i = 0; i < 3; ++i)
//             if(Sol[i] != equal[i]){
//                 printf("In test %d, Returned %d, but answer is %d\n", i+1, equal[i], Sol[i]);
//                 return 0;
//             }
//     }
//     return 0;
// }

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