oj.uz

Submission #745330

# Submission time Handle Problem Language Result Execution time Memory
745330 2023-05-19T21:32:15 Z Lobo Swapping Cities (APIO20_swap) C++17
13 / 100
 414 ms 50216 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(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

# Verdict Execution time Memory Grader output
1 Correct 6 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 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 168 ms 38672 KB Output is correct
10 Correct 186 ms 45508 KB Output is correct
11 Correct 199 ms 44556 KB Output is correct
12 Correct 201 ms 46960 KB Output is correct
13 Correct 176 ms 45748 KB Output is correct
14 Correct 152 ms 37888 KB Output is correct
15 Correct 242 ms 47700 KB Output is correct
16 Correct 236 ms 45448 KB Output is correct
17 Correct 250 ms 50216 KB Output is correct
18 Correct 205 ms 46312 KB Output is correct
19 Correct 109 ms 19288 KB Output is correct
20 Correct 397 ms 48360 KB Output is correct
21 Correct 414 ms 46456 KB Output is correct
22 Correct 414 ms 49956 KB Output is correct
23 Correct 404 ms 47332 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 211 ms 40832 KB Output is correct
4 Correct 208 ms 42280 KB Output is correct
5 Correct 220 ms 41428 KB Output is correct
6 Correct 208 ms 42076 KB Output is correct
7 Correct 209 ms 41936 KB Output is correct
8 Correct 204 ms 40676 KB Output is correct
9 Correct 205 ms 41576 KB Output is correct
10 Correct 220 ms 40436 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9912 KB Output is correct
11 Correct 7 ms 10068 KB Output is correct
12 Correct 6 ms 9940 KB Output is correct
13 Correct 7 ms 9960 KB Output is correct
14 Incorrect 6 ms 9940 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 168 ms 38672 KB Output is correct
11 Correct 186 ms 45508 KB Output is correct
12 Correct 199 ms 44556 KB Output is correct
13 Correct 201 ms 46960 KB Output is correct
14 Correct 176 ms 45748 KB Output is correct
15 Correct 6 ms 9912 KB Output is correct
16 Correct 7 ms 10068 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 7 ms 9960 KB Output is correct
19 Incorrect 6 ms 9940 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 9812 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 168 ms 38672 KB Output is correct
10 Correct 186 ms 45508 KB Output is correct
11 Correct 199 ms 44556 KB Output is correct
12 Correct 201 ms 46960 KB Output is correct
13 Correct 176 ms 45748 KB Output is correct
14 Correct 152 ms 37888 KB Output is correct
15 Correct 242 ms 47700 KB Output is correct
16 Correct 236 ms 45448 KB Output is correct
17 Correct 250 ms 50216 KB Output is correct
18 Correct 205 ms 46312 KB Output is correct
19 Correct 211 ms 40832 KB Output is correct
20 Correct 208 ms 42280 KB Output is correct
21 Correct 220 ms 41428 KB Output is correct
22 Correct 208 ms 42076 KB Output is correct
23 Correct 209 ms 41936 KB Output is correct
24 Correct 204 ms 40676 KB Output is correct
25 Correct 205 ms 41576 KB Output is correct
26 Correct 220 ms 40436 KB Output is correct
27 Correct 6 ms 9912 KB Output is correct
28 Correct 7 ms 10068 KB Output is correct
29 Correct 6 ms 9940 KB Output is correct
30 Correct 7 ms 9960 KB Output is correct
31 Incorrect 6 ms 9940 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 7 ms 9940 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 168 ms 38672 KB Output is correct
11 Correct 186 ms 45508 KB Output is correct
12 Correct 199 ms 44556 KB Output is correct
13 Correct 201 ms 46960 KB Output is correct
14 Correct 176 ms 45748 KB Output is correct
15 Correct 152 ms 37888 KB Output is correct
16 Correct 242 ms 47700 KB Output is correct
17 Correct 236 ms 45448 KB Output is correct
18 Correct 250 ms 50216 KB Output is correct
19 Correct 205 ms 46312 KB Output is correct
20 Correct 211 ms 40832 KB Output is correct
21 Correct 208 ms 42280 KB Output is correct
22 Correct 220 ms 41428 KB Output is correct
23 Correct 208 ms 42076 KB Output is correct
24 Correct 209 ms 41936 KB Output is correct
25 Correct 204 ms 40676 KB Output is correct
26 Correct 205 ms 41576 KB Output is correct
27 Correct 220 ms 40436 KB Output is correct
28 Correct 6 ms 9912 KB Output is correct
29 Correct 7 ms 10068 KB Output is correct
30 Correct 6 ms 9940 KB Output is correct
31 Correct 7 ms 9960 KB Output is correct
32 Incorrect 6 ms 9940 KB Output isn't correct
33 Halted 0 ms 0 KB -