oj.uz

답안 #894745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894745 2023-12-28T20:54:09 Z ShaShi 자매 도시 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 33440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 33440 KB Output isn't correct
2 Halted 0 ms 0 KB -