oj.uz

Submission #745340

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

}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 64 ms 19524 KB Output is correct
10 Correct 105 ms 21180 KB Output is correct
11 Correct 113 ms 21044 KB Output is correct
12 Correct 116 ms 21776 KB Output is correct
13 Correct 85 ms 19192 KB Output is correct
14 Execution timed out 2100 ms 19484 KB Time limit exceeded
15 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 9712 KB Output is correct
3 Execution timed out 2057 ms 19008 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 9712 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 5 ms 9812 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 9712 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 64 ms 19524 KB Output is correct
10 Correct 105 ms 21180 KB Output is correct
11 Correct 113 ms 21044 KB Output is correct
12 Correct 116 ms 21776 KB Output is correct
13 Correct 85 ms 19192 KB Output is correct
14 Execution timed out 2100 ms 19484 KB Time limit exceeded
15 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 -