oj.uz

Submission #745328

# Submission time Handle Problem Language Result Execution time Memory
745328 2023-05-19T21:23:14 Z Lobo Swapping Cities (APIO20_swap) C++17
13 / 100
 440 ms 54396 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;
    }

    int ans = -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,0);
    }



}

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;

}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:116:9: warning: unused variable 'ans' [-Wunused-variable]
  116 |     int ans = -1;
      |         ^~~

Subtask #1
6.0 / 6.0

# 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 9684 KB Output is correct
4 Correct 5 ms 9880 KB Output is correct
5 Correct 6 ms 10068 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 9976 KB Output is correct
9 Correct 141 ms 38528 KB Output is correct
10 Correct 188 ms 45456 KB Output is correct
11 Correct 183 ms 44752 KB Output is correct
12 Correct 190 ms 46908 KB Output is correct
13 Correct 169 ms 45616 KB Output is correct
14 Correct 139 ms 37944 KB Output is correct
15 Correct 232 ms 48968 KB Output is correct
16 Correct 227 ms 46512 KB Output is correct
17 Correct 253 ms 51628 KB Output is correct
18 Correct 208 ms 47648 KB Output is correct
19 Correct 102 ms 20420 KB Output is correct
20 Correct 408 ms 52480 KB Output is correct
21 Correct 413 ms 50752 KB Output is correct
22 Correct 422 ms 54396 KB Output is correct
23 Correct 440 ms 51752 KB Output is correct

Subtask #2
7.0 / 7.0

# 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 212 ms 40804 KB Output is correct
4 Correct 212 ms 44868 KB Output is correct
5 Correct 204 ms 43992 KB Output is correct
6 Correct 201 ms 45908 KB Output is correct
7 Correct 222 ms 45840 KB Output is correct
8 Correct 220 ms 44540 KB Output is correct
9 Correct 207 ms 45524 KB Output is correct
10 Correct 202 ms 44244 KB Output is correct

Subtask #3
0 / 17.0

# 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 9684 KB Output is correct
4 Correct 5 ms 9880 KB Output is correct
5 Correct 6 ms 10068 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 9976 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 5 ms 9940 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct
14 Incorrect 6 ms 9992 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 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 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9880 KB Output is correct
6 Correct 6 ms 10068 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 9976 KB Output is correct
10 Correct 141 ms 38528 KB Output is correct
11 Correct 188 ms 45456 KB Output is correct
12 Correct 183 ms 44752 KB Output is correct
13 Correct 190 ms 46908 KB Output is correct
14 Correct 169 ms 45616 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Correct 6 ms 10068 KB Output is correct
17 Correct 5 ms 9940 KB Output is correct
18 Correct 6 ms 9940 KB Output is correct
19 Incorrect 6 ms 9992 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 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 9684 KB Output is correct
4 Correct 5 ms 9880 KB Output is correct
5 Correct 6 ms 10068 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 9976 KB Output is correct
9 Correct 141 ms 38528 KB Output is correct
10 Correct 188 ms 45456 KB Output is correct
11 Correct 183 ms 44752 KB Output is correct
12 Correct 190 ms 46908 KB Output is correct
13 Correct 169 ms 45616 KB Output is correct
14 Correct 139 ms 37944 KB Output is correct
15 Correct 232 ms 48968 KB Output is correct
16 Correct 227 ms 46512 KB Output is correct
17 Correct 253 ms 51628 KB Output is correct
18 Correct 208 ms 47648 KB Output is correct
19 Correct 212 ms 40804 KB Output is correct
20 Correct 212 ms 44868 KB Output is correct
21 Correct 204 ms 43992 KB Output is correct
22 Correct 201 ms 45908 KB Output is correct
23 Correct 222 ms 45840 KB Output is correct
24 Correct 220 ms 44540 KB Output is correct
25 Correct 207 ms 45524 KB Output is correct
26 Correct 202 ms 44244 KB Output is correct
27 Correct 6 ms 9940 KB Output is correct
28 Correct 6 ms 10068 KB Output is correct
29 Correct 5 ms 9940 KB Output is correct
30 Correct 6 ms 9940 KB Output is correct
31 Incorrect 6 ms 9992 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 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 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9880 KB Output is correct
6 Correct 6 ms 10068 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 9976 KB Output is correct
10 Correct 141 ms 38528 KB Output is correct
11 Correct 188 ms 45456 KB Output is correct
12 Correct 183 ms 44752 KB Output is correct
13 Correct 190 ms 46908 KB Output is correct
14 Correct 169 ms 45616 KB Output is correct
15 Correct 139 ms 37944 KB Output is correct
16 Correct 232 ms 48968 KB Output is correct
17 Correct 227 ms 46512 KB Output is correct
18 Correct 253 ms 51628 KB Output is correct
19 Correct 208 ms 47648 KB Output is correct
20 Correct 212 ms 40804 KB Output is correct
21 Correct 212 ms 44868 KB Output is correct
22 Correct 204 ms 43992 KB Output is correct
23 Correct 201 ms 45908 KB Output is correct
24 Correct 222 ms 45840 KB Output is correct
25 Correct 220 ms 44540 KB Output is correct
26 Correct 207 ms 45524 KB Output is correct
27 Correct 202 ms 44244 KB Output is correct
28 Correct 6 ms 9940 KB Output is correct
29 Correct 6 ms 10068 KB Output is correct
30 Correct 5 ms 9940 KB Output is correct
31 Correct 6 ms 9940 KB Output is correct
32 Incorrect 6 ms 9992 KB Output isn't correct
33 Halted 0 ms 0 KB -