oj.uz

Submission #563394

# Submission time Handle Problem Language Result Execution time Memory
563394 2022-05-17T06:17:29 Z AA_Surely Swapping Cities (APIO20_swap) C++14
0 / 100
 4 ms 8532 KB 
#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);

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -