oj.uz

Submission #395204

# Submission time Handle Problem Language Result Execution time Memory
395204 2021-04-28T02:10:09 Z Erkhemkhuu Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 5928 KB 
#include <bits/stdc++.h>
using namespace std;
const int bigN = 100005;
const int lg = 18;
int tin[bigN], tout[bigN];
int depth[bigN], timer, anc[bigN][lg];
int n, m;
int par[bigN], sz[bigN], cnt[bigN];
bool done[bigN];
vector <tuple <int, int, int> > edges;
/*
bool is_ancestor(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int go_up(int v, int u) {
    for(int i = lg - 1; i >= 0; i--)
        if(!is_ancestor(anc[v][i], u))
            v = anc[v][i];
    return v;
}
void dfs(int v, int p) {
    tin[v] = ++timer;
    anc[v][0] = p;
    for(int i = 1; i < lg; i++)
        anc[v][i] = anc[anc[v][i - 1]][i - 1];
    for(auto &u: v) {
        if(u == p) continue;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
    tout[v] = ++timer;
    return;
}
int lca(int v, int u) {
    if(is_ancestor(v, u)) return v;
    if(is_ancestor(u, v)) return u;
    return anc[go_up(v, u)][0];
}
*/
int get(int x) {
    return ((x == par[x]) ? (x) : (par[x] = get(par[x])));
}
void init(int N, int M, vector <int> V, vector <int> U, vector <int> W) {
    n = N; m = M;
    for(int i = 0; i < m; i++)
        edges.push_back({W[i], V[i], U[i]});
    return;
}
void prepare() {
    for(int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
        cnt[i] = 0;
        done[i] = false;
    }
    return;
}
int getMinimumFuelCapacity(int v, int u) {
    prepare();
    sort(edges.begin(), edges.end());
    for(auto &it: edges) {
        int x, y, z;
        tie(z, x, y) = it;
        cnt[x]++; cnt[y]++;

        int X = get(x);
        int Y = get(Y);

        bool flag = (X == Y);
        flag |= (cnt[x] >= 3 || cnt[y] >= 3);
        if(flag) done[X] = true;

        if(sz[X] < sz[Y]) swap(X, Y);
        sz[X] += sz[Y];
        done[X] |= done[Y];
        par[Y] = X;

        if(get(v) == get(u) && done[get(v)])
            return z;
    }
    return -1;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:41:24: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     return ((x == par[x]) ? (x) : (par[x] = get(par[x])));
      |                   ~~~~~^
swap.cpp:67:13: note: 'Y' was declared here
   67 |         int Y = get(Y);
      |             ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -