oj.uz

Submission #745367

# Submission time Handle Problem Language Result Execution time Memory
745367 2023-05-19T22:06:18 Z Lobo Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 50660 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;
}


int ds1[maxn], dsz1[maxn];
int find1(int u) {
    if(ds1[u] == u) return u;
    return ds1[u] = find1(ds1[u]);
}

void join1(int u, int v) {
    u = find1(u);
    v = find1(v);
    if(u == v) return;

    if(dsz1[u] < dsz1[v]) swap(u,v);
    dsz1[u]+= dsz1[v];
    ds1[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;
}

int cu[maxn];
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++) cu[i] = mn[i];
    dfs(0,0,-1);
}

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

    int ans = -1;
    for(int i = 0; i < m; i++) {
        int u = edgs[i].sc.fr;
        int v = edgs[i].sc.sc;
        join1(u,v);
        if(find1(x) == find1(y) && ans == -1) ans = i;
    }
    if(ans == -1) return -1;
    return edgs[max({ans,mn[x],mn[y]})].fr;

}

Subtask #1
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 6 ms 9744 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 138 ms 38860 KB Output is correct
10 Correct 182 ms 46052 KB Output is correct
11 Correct 172 ms 45032 KB Output is correct
12 Correct 187 ms 47364 KB Output is correct
13 Correct 173 ms 46024 KB Output is correct
14 Correct 140 ms 38208 KB Output is correct
15 Correct 225 ms 48084 KB Output is correct
16 Correct 230 ms 45676 KB Output is correct
17 Correct 240 ms 50660 KB Output is correct
18 Correct 209 ms 46760 KB Output is correct
19 Execution timed out 2086 ms 17692 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
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 Execution timed out 2077 ms 39752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

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 6 ms 9744 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 Incorrect 6 ms 9940 KB Output isn't correct
11 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 6 ms 9744 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 138 ms 38860 KB Output is correct
11 Correct 182 ms 46052 KB Output is correct
12 Correct 172 ms 45032 KB Output is correct
13 Correct 187 ms 47364 KB Output is correct
14 Correct 173 ms 46024 KB Output is correct
15 Incorrect 6 ms 9940 KB Output isn't correct
16 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 6 ms 9744 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 138 ms 38860 KB Output is correct
10 Correct 182 ms 46052 KB Output is correct
11 Correct 172 ms 45032 KB Output is correct
12 Correct 187 ms 47364 KB Output is correct
13 Correct 173 ms 46024 KB Output is correct
14 Correct 140 ms 38208 KB Output is correct
15 Correct 225 ms 48084 KB Output is correct
16 Correct 230 ms 45676 KB Output is correct
17 Correct 240 ms 50660 KB Output is correct
18 Correct 209 ms 46760 KB Output is correct
19 Execution timed out 2077 ms 39752 KB Time limit exceeded
20 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 6 ms 9744 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 138 ms 38860 KB Output is correct
11 Correct 182 ms 46052 KB Output is correct
12 Correct 172 ms 45032 KB Output is correct
13 Correct 187 ms 47364 KB Output is correct
14 Correct 173 ms 46024 KB Output is correct
15 Correct 140 ms 38208 KB Output is correct
16 Correct 225 ms 48084 KB Output is correct
17 Correct 230 ms 45676 KB Output is correct
18 Correct 240 ms 50660 KB Output is correct
19 Correct 209 ms 46760 KB Output is correct
20 Execution timed out 2077 ms 39752 KB Time limit exceeded
21 Halted 0 ms 0 KB -