oj.uz

답안 #745329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745329 2023-05-19T21:27:42 Z Lobo 자매 도시 (APIO20_swap) C++17
13 / 100
 443 ms 50404 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int lg = 20;

int n, m, gr[maxn], ds[maxn], dsz[maxn], mn[maxn];
vector<int> mn0[maxn];
vector<pair<int,pair<int,int>>> edgs;
int p[maxn][lg+2], w[maxn][lg+2], h[maxn];
vector<pair<int,int>> g[maxn];

int find(int u) {
    if(ds[u] == u) return u;
    return ds[u] = find(ds[u]);
}

void join(int u, int v, int id) {
    gr[u]++;
    gr[v]++;
    int mxgr = max(gr[u],gr[v]);

    u = find(u);
    v = find(v);

    if(u == v || mxgr >= 3 || mn[u] != -1 || mn[v] != -1) {
        if(mn0[u].size()) {
            for(auto x : mn0[u]) {
                mn[x] = id;
            }
            mn0[u].clear();
        }
        if(mn0[v].size()) {
            for(auto x : mn0[v]) {
                mn[x] = id;
            }
            mn0[v].clear();
        }
    }
    if(u == v) return;

    if(dsz[u] < dsz[v]) swap(u,v);

    for(auto x : mn0[v]) {
        mn0[u].pb(x);
    }

    dsz[u]+= dsz[v];
    ds[v] = u;
}

void dfs(int u, int ant, int antw) {
    p[u][0] = ant;
    w[u][0] = antw;

    for(int i = 1; i <= lg; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
        w[u][i] = max(w[u][i-1],w[p[u][i-1]][i-1]);
    }

    for(auto V : g[u]) if(V.fr != ant) {
        h[V.fr] = h[u]+1;
        dfs(V.fr,u,V.sc);
    }
}

int lca(int u, int v) {
    int ans = 0;
    if(h[u] < h[v]) swap(u,v);

    for(int i = lg; i >= 0; i--) {
        if(h[p[u][i]] >= h[v]) {
            ans = max(ans, w[u][i]);
            u = p[u][i];
        }
    }
    if(u == v) return ans;

    for(int i = lg; i >= 0; i--) {
        if(p[u][i] != p[v][i]) {
            ans = max(ans,w[u][i]);
            u = p[u][i];
            ans = max(ans,w[v][i]);
            v = p[v][i];
        }
    }
    ans = max(ans, w[u][0]);
    return ans;
}

void init(int N, int M, vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;

    for(auto i = 0; i < m; i++) {
        edgs.pb(mp(W[i],mp(U[i],V[i])));
    }

    sort(all(edgs));

    for(int i = 0; i < n; i++) {
        gr[i] = 0;
        mn[i] = -1;
        ds[i] = i;
        dsz[i] = 1;
        mn0[i].clear();
        mn0[i].pb(i);
        p[i][0] = -1;
    }

    for(int i = 0; i < m; i++) {
        int u = edgs[i].sc.fr;
        int v = edgs[i].sc.sc;
        if(find(u) != find(v)) {
            g[u].pb(mp(v,i));
            g[v].pb(mp(u,i));
        }
        join(u,v,i);
    }

    for(int i = 0; i < n; i++) {
        if(p[i][0] == -1) dfs(i,i,-1);
    }



}

int getMinimumFuelCapacity(int x, int y) {
    if(find(x) != find(y) || mn[x] == -1 || mn[y] == -1) return -1;

    return edgs[max({lca(x,y),mn[x],mn[y]})].fr;

}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9736 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 134 ms 38528 KB Output is correct
10 Correct 191 ms 45520 KB Output is correct
11 Correct 183 ms 44564 KB Output is correct
12 Correct 187 ms 46912 KB Output is correct
13 Correct 161 ms 45648 KB Output is correct
14 Correct 136 ms 37952 KB Output is correct
15 Correct 235 ms 47700 KB Output is correct
16 Correct 240 ms 45296 KB Output is correct
17 Correct 271 ms 50404 KB Output is correct
18 Correct 204 ms 46328 KB Output is correct
19 Correct 105 ms 19140 KB Output is correct
20 Correct 410 ms 48324 KB Output is correct
21 Correct 443 ms 46460 KB Output is correct
22 Correct 422 ms 49884 KB Output is correct
23 Correct 377 ms 47400 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 190 ms 40884 KB Output is correct
4 Correct 199 ms 42236 KB Output is correct
5 Correct 204 ms 41632 KB Output is correct
6 Correct 210 ms 42100 KB Output is correct
7 Correct 212 ms 41848 KB Output is correct
8 Correct 191 ms 40696 KB Output is correct
9 Correct 201 ms 41640 KB Output is correct
10 Correct 198 ms 40440 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9736 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 7 ms 9940 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 6 ms 9940 KB Output is correct
13 Correct 5 ms 9940 KB Output is correct
14 Incorrect 5 ms 9940 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9736 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 6 ms 10068 KB Output is correct
10 Correct 134 ms 38528 KB Output is correct
11 Correct 191 ms 45520 KB Output is correct
12 Correct 183 ms 44564 KB Output is correct
13 Correct 187 ms 46912 KB Output is correct
14 Correct 161 ms 45648 KB Output is correct
15 Correct 7 ms 9940 KB Output is correct
16 Correct 6 ms 10068 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 5 ms 9940 KB Output is correct
19 Incorrect 5 ms 9940 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9736 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 134 ms 38528 KB Output is correct
10 Correct 191 ms 45520 KB Output is correct
11 Correct 183 ms 44564 KB Output is correct
12 Correct 187 ms 46912 KB Output is correct
13 Correct 161 ms 45648 KB Output is correct
14 Correct 136 ms 37952 KB Output is correct
15 Correct 235 ms 47700 KB Output is correct
16 Correct 240 ms 45296 KB Output is correct
17 Correct 271 ms 50404 KB Output is correct
18 Correct 204 ms 46328 KB Output is correct
19 Correct 190 ms 40884 KB Output is correct
20 Correct 199 ms 42236 KB Output is correct
21 Correct 204 ms 41632 KB Output is correct
22 Correct 210 ms 42100 KB Output is correct
23 Correct 212 ms 41848 KB Output is correct
24 Correct 191 ms 40696 KB Output is correct
25 Correct 201 ms 41640 KB Output is correct
26 Correct 198 ms 40440 KB Output is correct
27 Correct 7 ms 9940 KB Output is correct
28 Correct 6 ms 10068 KB Output is correct
29 Correct 6 ms 9940 KB Output is correct
30 Correct 5 ms 9940 KB Output is correct
31 Incorrect 5 ms 9940 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9736 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 6 ms 10068 KB Output is correct
10 Correct 134 ms 38528 KB Output is correct
11 Correct 191 ms 45520 KB Output is correct
12 Correct 183 ms 44564 KB Output is correct
13 Correct 187 ms 46912 KB Output is correct
14 Correct 161 ms 45648 KB Output is correct
15 Correct 136 ms 37952 KB Output is correct
16 Correct 235 ms 47700 KB Output is correct
17 Correct 240 ms 45296 KB Output is correct
18 Correct 271 ms 50404 KB Output is correct
19 Correct 204 ms 46328 KB Output is correct
20 Correct 190 ms 40884 KB Output is correct
21 Correct 199 ms 42236 KB Output is correct
22 Correct 204 ms 41632 KB Output is correct
23 Correct 210 ms 42100 KB Output is correct
24 Correct 212 ms 41848 KB Output is correct
25 Correct 191 ms 40696 KB Output is correct
26 Correct 201 ms 41640 KB Output is correct
27 Correct 198 ms 40440 KB Output is correct
28 Correct 7 ms 9940 KB Output is correct
29 Correct 6 ms 10068 KB Output is correct
30 Correct 6 ms 9940 KB Output is correct
31 Correct 5 ms 9940 KB Output is correct
32 Incorrect 5 ms 9940 KB Output isn't correct
33 Halted 0 ms 0 KB -