oj.uz

Submission #745332

# Submission time Handle Problem Language Result Execution time Memory
745332 2023-05-19T21:36:07 Z Lobo Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 50304 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] = find(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;
}

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;

    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;
    }

    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 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 10132 KB Output is correct
6 Correct 6 ms 10044 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 5 ms 10068 KB Output is correct
9 Correct 137 ms 38600 KB Output is correct
10 Correct 185 ms 45664 KB Output is correct
11 Correct 179 ms 44668 KB Output is correct
12 Correct 192 ms 46896 KB Output is correct
13 Correct 164 ms 45688 KB Output is correct
14 Correct 140 ms 38012 KB Output is correct
15 Correct 239 ms 47784 KB Output is correct
16 Correct 234 ms 45264 KB Output is correct
17 Correct 248 ms 50304 KB Output is correct
18 Correct 208 ms 46292 KB Output is correct
19 Execution timed out 2095 ms 17628 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 2054 ms 39368 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 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 10132 KB Output is correct
6 Correct 6 ms 10044 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 5 ms 10068 KB Output is correct
9 Correct 5 ms 9812 KB Output is correct
10 Incorrect 7 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 9812 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 9812 KB Output is correct
6 Correct 6 ms 10132 KB Output is correct
7 Correct 6 ms 10044 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 5 ms 10068 KB Output is correct
10 Correct 137 ms 38600 KB Output is correct
11 Correct 185 ms 45664 KB Output is correct
12 Correct 179 ms 44668 KB Output is correct
13 Correct 192 ms 46896 KB Output is correct
14 Correct 164 ms 45688 KB Output is correct
15 Incorrect 7 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 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 10132 KB Output is correct
6 Correct 6 ms 10044 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 5 ms 10068 KB Output is correct
9 Correct 137 ms 38600 KB Output is correct
10 Correct 185 ms 45664 KB Output is correct
11 Correct 179 ms 44668 KB Output is correct
12 Correct 192 ms 46896 KB Output is correct
13 Correct 164 ms 45688 KB Output is correct
14 Correct 140 ms 38012 KB Output is correct
15 Correct 239 ms 47784 KB Output is correct
16 Correct 234 ms 45264 KB Output is correct
17 Correct 248 ms 50304 KB Output is correct
18 Correct 208 ms 46292 KB Output is correct
19 Execution timed out 2054 ms 39368 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 9812 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 9812 KB Output is correct
6 Correct 6 ms 10132 KB Output is correct
7 Correct 6 ms 10044 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 5 ms 10068 KB Output is correct
10 Correct 137 ms 38600 KB Output is correct
11 Correct 185 ms 45664 KB Output is correct
12 Correct 179 ms 44668 KB Output is correct
13 Correct 192 ms 46896 KB Output is correct
14 Correct 164 ms 45688 KB Output is correct
15 Correct 140 ms 38012 KB Output is correct
16 Correct 239 ms 47784 KB Output is correct
17 Correct 234 ms 45264 KB Output is correct
18 Correct 248 ms 50304 KB Output is correct
19 Correct 208 ms 46292 KB Output is correct
20 Execution timed out 2054 ms 39368 KB Time limit exceeded
21 Halted 0 ms 0 KB -