oj.uz

Submission #745349

# Submission time Handle Problem Language Result Execution time Memory
745349 2023-05-19T21:56:11 Z Lobo Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 50272 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) {
    // 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);
    //     if(find(u) == find(v) && mn[u] != -1 && mn[v] != -1) return edgs[i].fr;
    // }






    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 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 6 ms 9968 KB Output is correct
6 Correct 6 ms 9984 KB Output is correct
7 Correct 6 ms 10004 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 174 ms 38500 KB Output is correct
10 Correct 178 ms 45524 KB Output is correct
11 Correct 172 ms 44656 KB Output is correct
12 Correct 200 ms 47048 KB Output is correct
13 Correct 175 ms 45696 KB Output is correct
14 Correct 144 ms 37984 KB Output is correct
15 Correct 231 ms 47712 KB Output is correct
16 Correct 232 ms 45348 KB Output is correct
17 Correct 259 ms 50272 KB Output is correct
18 Correct 209 ms 46304 KB Output is correct
19 Execution timed out 2081 ms 17632 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 2045 ms 39364 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 9968 KB Output is correct
6 Correct 6 ms 9984 KB Output is correct
7 Correct 6 ms 10004 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 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 9968 KB Output is correct
6 Correct 6 ms 9984 KB Output is correct
7 Correct 6 ms 10004 KB Output is correct
8 Correct 7 ms 10068 KB Output is correct
9 Correct 174 ms 38500 KB Output is correct
10 Correct 178 ms 45524 KB Output is correct
11 Correct 172 ms 44656 KB Output is correct
12 Correct 200 ms 47048 KB Output is correct
13 Correct 175 ms 45696 KB Output is correct
14 Correct 144 ms 37984 KB Output is correct
15 Correct 231 ms 47712 KB Output is correct
16 Correct 232 ms 45348 KB Output is correct
17 Correct 259 ms 50272 KB Output is correct
18 Correct 209 ms 46304 KB Output is correct
19 Execution timed out 2045 ms 39364 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -