Submission #745331

# Submission time Handle Problem Language Result Execution time Memory
745331 2023-05-19T21:32:36 Z Lobo Swapping Cities (APIO20_swap) C++17
13 / 100
434 ms 50268 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);
    }
    dfs(0,0,-1);
}

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

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

}
# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9696 KB Output is correct
3 Correct 5 ms 9616 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 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 139 ms 38688 KB Output is correct
10 Correct 180 ms 45504 KB Output is correct
11 Correct 189 ms 44608 KB Output is correct
12 Correct 195 ms 46960 KB Output is correct
13 Correct 168 ms 45688 KB Output is correct
14 Correct 149 ms 37952 KB Output is correct
15 Correct 228 ms 47716 KB Output is correct
16 Correct 232 ms 45324 KB Output is correct
17 Correct 254 ms 50268 KB Output is correct
18 Correct 206 ms 46256 KB Output is correct
19 Correct 99 ms 19160 KB Output is correct
20 Correct 410 ms 48424 KB Output is correct
21 Correct 434 ms 46560 KB Output is correct
22 Correct 422 ms 49912 KB Output is correct
23 Correct 398 ms 47332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9696 KB Output is correct
3 Correct 206 ms 40804 KB Output is correct
4 Correct 210 ms 42280 KB Output is correct
5 Correct 225 ms 41580 KB Output is correct
6 Correct 205 ms 42220 KB Output is correct
7 Correct 215 ms 41832 KB Output is correct
8 Correct 202 ms 40688 KB Output is correct
9 Correct 218 ms 41632 KB Output is correct
10 Correct 208 ms 40524 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9696 KB Output is correct
3 Correct 5 ms 9616 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 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 6 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 -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9696 KB Output is correct
4 Correct 5 ms 9616 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 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 139 ms 38688 KB Output is correct
11 Correct 180 ms 45504 KB Output is correct
12 Correct 189 ms 44608 KB Output is correct
13 Correct 195 ms 46960 KB Output is correct
14 Correct 168 ms 45688 KB Output is correct
15 Correct 6 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 -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9696 KB Output is correct
3 Correct 5 ms 9616 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 5 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 139 ms 38688 KB Output is correct
10 Correct 180 ms 45504 KB Output is correct
11 Correct 189 ms 44608 KB Output is correct
12 Correct 195 ms 46960 KB Output is correct
13 Correct 168 ms 45688 KB Output is correct
14 Correct 149 ms 37952 KB Output is correct
15 Correct 228 ms 47716 KB Output is correct
16 Correct 232 ms 45324 KB Output is correct
17 Correct 254 ms 50268 KB Output is correct
18 Correct 206 ms 46256 KB Output is correct
19 Correct 206 ms 40804 KB Output is correct
20 Correct 210 ms 42280 KB Output is correct
21 Correct 225 ms 41580 KB Output is correct
22 Correct 205 ms 42220 KB Output is correct
23 Correct 215 ms 41832 KB Output is correct
24 Correct 202 ms 40688 KB Output is correct
25 Correct 218 ms 41632 KB Output is correct
26 Correct 208 ms 40524 KB Output is correct
27 Correct 6 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 -
# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9696 KB Output is correct
4 Correct 5 ms 9616 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 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 139 ms 38688 KB Output is correct
11 Correct 180 ms 45504 KB Output is correct
12 Correct 189 ms 44608 KB Output is correct
13 Correct 195 ms 46960 KB Output is correct
14 Correct 168 ms 45688 KB Output is correct
15 Correct 149 ms 37952 KB Output is correct
16 Correct 228 ms 47716 KB Output is correct
17 Correct 232 ms 45324 KB Output is correct
18 Correct 254 ms 50268 KB Output is correct
19 Correct 206 ms 46256 KB Output is correct
20 Correct 206 ms 40804 KB Output is correct
21 Correct 210 ms 42280 KB Output is correct
22 Correct 225 ms 41580 KB Output is correct
23 Correct 205 ms 42220 KB Output is correct
24 Correct 215 ms 41832 KB Output is correct
25 Correct 202 ms 40688 KB Output is correct
26 Correct 218 ms 41632 KB Output is correct
27 Correct 208 ms 40524 KB Output is correct
28 Correct 6 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 -