Submission #563396

#	Time	Username	Problem	Language	Result	Execution time	Memory
563396		AA_Surely	Swapping Cities (APIO20_swap)	C++14	100 / 100	359 ms	65352 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 3e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

struct Edge {
    int sp, ep, val;

    inline bool operator < (const Edge &other) {
        return val < other.val;
    }
} eset[N];

int n, m;
int par[N], weight[N], height[N];
int deg[N], ans[N], up[N][LOG];
bool possible[N];
VI adj[N];

int grand(int x) {
    if (par[x] < 0) return x;
    return par[x] = grand(par[x]);
}

inline void merge(int a, int b, int x) {
    deg[a]++; deg[b]++;
    if (deg[a] >= 3 || deg[b] >= 3) possible[n] = 1;

    a = grand(a); b = grand(b);

    possible[n] |= possible[a] | possible[b];

    adj[n].pb(a);
    if (a != b) adj[n].pb(b);
    else possible[n] = 1;

    weight[n] = x;

    par[a] = par[b] = n;
    n++;
    return;
}

void dfs(int now = n - 1, int best = INF, int h = 0) {
    if (possible[now]) best = weight[now];
    ans[now] = best;
    height[now] = h;

    for(int on : adj[now]) {
        dfs(on, best, h + 1);
        up[on][0] = now;
    }

    return;
}

void precalc() {
    up[n - 1][0] = up[n][0] = 0;
    FOR(k, 1, LOG) F0R(i, n + 1) 
        up[i][k] = up[ up[i][k - 1] ][k - 1];

    return;
}

inline int lca(int a, int b) {
    if (height[a] < height[b]) swap(a, b);
    R0F(i, LOG) if (height[a] - (1 << i) >= height[b]) 
        a = up[a][i];
    if (a == b) return a;

    R0F(i, LOG) if (up[a][i] != up[b][i]) {
        a = up[a][i];
        b = up[b][i];
    }

    return up[a][0];
}

void init(int p, int q, VI us, VI vs, VI ws) {
    n = p; m = q;
    F0R(i, m) {
        eset[i].sp = us[i];
        eset[i].ep = vs[i];
        eset[i].val = ws[i];
    }
    
    fill(par, par + N, -1);
    sort(eset, eset + m);
    F0R(i, m) merge(eset[i].sp, eset[i].ep, eset[i].val);

    dfs();
    precalc();
}

int getMinimumFuelCapacity(int x, int y) {
    int z = lca(x, y);

    return (ans[z] == INF ? -1 : ans[z]);
}

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