oj.uz

Submission #745343

# Submission time Handle Problem Language Result Execution time Memory
745343 2023-05-19T21:53:33 Z Lobo Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 15884 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);
    // }

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

    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[x] != -1 && mn[y] != -1) return edgs[i].fr;
    }
    return -1;

}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 58 ms 13832 KB Output is correct
10 Correct 95 ms 15320 KB Output is correct
11 Correct 105 ms 15296 KB Output is correct
12 Correct 111 ms 15884 KB Output is correct
13 Correct 83 ms 13260 KB Output is correct
14 Execution timed out 2080 ms 13956 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 2045 ms 13796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Incorrect 3 ms 5076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 58 ms 13832 KB Output is correct
11 Correct 95 ms 15320 KB Output is correct
12 Correct 105 ms 15296 KB Output is correct
13 Correct 111 ms 15884 KB Output is correct
14 Correct 83 ms 13260 KB Output is correct
15 Incorrect 3 ms 5076 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 58 ms 13832 KB Output is correct
10 Correct 95 ms 15320 KB Output is correct
11 Correct 105 ms 15296 KB Output is correct
12 Correct 111 ms 15884 KB Output is correct
13 Correct 83 ms 13260 KB Output is correct
14 Execution timed out 2080 ms 13956 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 58 ms 13832 KB Output is correct
11 Correct 95 ms 15320 KB Output is correct
12 Correct 105 ms 15296 KB Output is correct
13 Correct 111 ms 15884 KB Output is correct
14 Correct 83 ms 13260 KB Output is correct
15 Execution timed out 2080 ms 13956 KB Time limit exceeded
16 Halted 0 ms 0 KB -