oj.uz

Submission #894744

# Submission time Handle Problem Language Result Execution time Memory
894744 2023-12-28T20:53:43 Z ShaShi Swapping Cities (APIO20_swap) C++17
0 / 100
 171 ms 64156 KB 
#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;


const int MAXN = (int)1e6 + 7;
const int LG = 18;
const int MOD = 998244353;
const int INF = (int)1e9 + 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) {
    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 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++) {
		u = U[i]+1;
		v = V[i]+1;
		w = W[i]+1;

        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);

    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, Y)]];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31356 KB Output is correct
7 Correct 6 ms 31764 KB Output is correct
8 Correct 6 ms 31384 KB Output is correct
9 Correct 63 ms 49096 KB Output is correct
10 Correct 62 ms 53932 KB Output is correct
11 Correct 64 ms 53960 KB Output is correct
12 Correct 65 ms 56552 KB Output is correct
13 Correct 67 ms 59588 KB Output is correct
14 Correct 55 ms 49096 KB Output is correct
15 Correct 153 ms 57924 KB Output is correct
16 Correct 117 ms 55752 KB Output is correct
17 Correct 126 ms 58160 KB Output is correct
18 Correct 170 ms 61400 KB Output is correct
19 Incorrect 65 ms 40212 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Incorrect 171 ms 64156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31356 KB Output is correct
7 Correct 6 ms 31764 KB Output is correct
8 Correct 6 ms 31384 KB Output is correct
9 Incorrect 7 ms 33368 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31356 KB Output is correct
7 Correct 6 ms 31764 KB Output is correct
8 Correct 6 ms 31384 KB Output is correct
9 Correct 63 ms 49096 KB Output is correct
10 Correct 62 ms 53932 KB Output is correct
11 Correct 64 ms 53960 KB Output is correct
12 Correct 65 ms 56552 KB Output is correct
13 Correct 67 ms 59588 KB Output is correct
14 Correct 55 ms 49096 KB Output is correct
15 Correct 153 ms 57924 KB Output is correct
16 Correct 117 ms 55752 KB Output is correct
17 Correct 126 ms 58160 KB Output is correct
18 Correct 170 ms 61400 KB Output is correct
19 Incorrect 171 ms 64156 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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