oj.uz

Submission #894745

# Submission time Handle Problem Language Result Execution time Memory
894745 2023-12-28T20:54:09 Z ShaShi Swapping Cities (APIO20_swap) C++17
0 / 100
 181 ms 64096 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+1, Y+1)]];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31320 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 31460 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31408 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 49 ms 48848 KB Output is correct
10 Correct 66 ms 54172 KB Output is correct
11 Correct 61 ms 53792 KB Output is correct
12 Correct 65 ms 56448 KB Output is correct
13 Correct 61 ms 59544 KB Output is correct
14 Correct 60 ms 49092 KB Output is correct
15 Correct 133 ms 58000 KB Output is correct
16 Correct 117 ms 55568 KB Output is correct
17 Correct 144 ms 58160 KB Output is correct
18 Correct 181 ms 61492 KB Output is correct
19 Incorrect 60 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 31320 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Incorrect 139 ms 64096 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 31320 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 31460 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31408 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Incorrect 7 ms 33440 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 33440 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 31320 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 31460 KB Output is correct
5 Correct 7 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31408 KB Output is correct
8 Correct 6 ms 31320 KB Output is correct
9 Correct 49 ms 48848 KB Output is correct
10 Correct 66 ms 54172 KB Output is correct
11 Correct 61 ms 53792 KB Output is correct
12 Correct 65 ms 56448 KB Output is correct
13 Correct 61 ms 59544 KB Output is correct
14 Correct 60 ms 49092 KB Output is correct
15 Correct 133 ms 58000 KB Output is correct
16 Correct 117 ms 55568 KB Output is correct
17 Correct 144 ms 58160 KB Output is correct
18 Correct 181 ms 61492 KB Output is correct
19 Incorrect 139 ms 64096 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 33440 KB Output isn't correct
2 Halted 0 ms 0 KB -