Submission #894746

#	Time	Username	Problem	Language	Result	Execution time	Memory
894746		ShaShi	Swapping Cities (APIO20_swap)	C++17	100 / 100	221 ms	70724 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
 
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int LG = 18;
const int MOD = 998244353;
const int INF = (int)1e18 + 7;
 
 
 
int n, m, t, flag, k, u, v, w, ans, ans2, tmp, tmp2, tmp3, tmp4, q, timer;
int arr[MAXN], num[MAXN];
int par[MAXN], love[MAXN], dp[MAXN], deg[MAXN];
int h[MAXN], dad[MAXN], pow2dad[MAXN][LG];
vector<pair<int, pii> > edge;
vector<int> adj[MAXN];
 
 
/* DSU */
 
inline int get_par(int v) {
    return (par[v] == v? v : par[v] = get_par(par[v]));
}
 
 
void unite(int u, int v, int w) {
    int u2, v2;
    u2 = u;
    v2 = v;
 
    deg[u2]++, deg[v2]++;
 
    u = get_par(u), v = get_par(v);
 
    if (u == v) {
        if (!love[u]) {
            love[u] = 1;
            num[u] = w;
        }
    } else {
        par[u] = par[v] = flag;
        par[flag] = flag;
        adj[flag].pb(u), adj[flag].pb(v);
        num[flag] = w;
 
        if (love[u] || love[v]) {
            love[flag] = 1;
        } else {
            love[flag] = (deg[u2] == 3 || deg[v2] == 3);
        }
 
        // cout << "@" << flag << " " << u << " " << v << endl;
 
        flag++;
    }
 
}
 
/* DSU */
 
/* LCA */
 
inline int up(int v, int k) {
    for (int i=LG-1; i>=0; i--) {
        if ((1<<i) <= k) {
            k -= (1<<i);
            v = pow2dad[v][i];
        }
    }
 
    return v;
}
 
 
int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
 
    u = up(u, h[u]-h[v]);
 
    for (int i=LG-1; i>=0; i--) {
        if (h[v] >= (1<<i) && pow2dad[v][i] != pow2dad[u][i]) {
            v = pow2dad[v][i];
            u = pow2dad[u][i];
        }
    }
 
    if (u == v) return u;
    return dad[v];
}
 
 
/* LCA */
 
 
// void DFS(int v) {
//     for (int u:adj[v]) {
//         if (u != dad[v]) {
//             dad[u] = v;
//             h[u] = h[v]+1;
//             DFS(u);
 
//             love[v] |= love[u];
//         }
//     }
 
//     dp[v] = (love[v]? v : dp[dad[v]]);
// }
 
void DFS(int v) {
    dp[v] = (love[v]? v : dp[dad[v]]);
 
    for (int u:adj[v]) {
        if (u != dad[v]) {
            dad[u] = v;
            h[u] = h[v]+1;
            DFS(u);
        }
    }
}
 
 
 
void DFS2(int v) {
    dp[v] = (love[v]? v : dp[dad[v]]);
 
    for (int u:adj[v]) if (u != dad[v]) DFS2(u);
}
 
 
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
 
	for (int i=0; i<m; i++) {
        // cin >> u >> v >> w;
		u = U[i]+1;
		v = V[i]+1;
		w = W[i];
 
        edge.pb(mp(w, mp(u, v)));
    }
 
    sort(all(edge));
    flag = n+1;
 
    for (int i=1; i<=n; i++) par[i] = i;
    
    for (int i=0; i<m; i++) unite(edge[i].S.F, edge[i].S.S, edge[i].F);
    flag--;
 
    DFS(flag);
    // DFS2(flag);
 
    for (int i=1; i<=flag; i++) pow2dad[i][0] = dad[i];
    for (int j=1; j<LG; j++) for (int i=1; i<=flag; i++) pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];
    num[0]--;
}
 
int getMinimumFuelCapacity(int X, int Y) {
	return num[dp[LCA(X+1, Y+1)]];
}

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