oj.uz

Submission #406433

# Submission time Handle Problem Language Result Execution time Memory
406433 2021-05-17T15:15:40 Z tengiz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 53668 KB 
#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 3e5 + 5;
int n, m;
int up[N][20], f[N], ans[N], tin[N], tout[N];
std::vector<int> e[N], to[N];
struct desu{
    std::vector<int> p;
    desu(int n){
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
    }
    int leader(int u){
        while (p[u] != u) u = p[u] = p[p[u]];
        return u;
    }
    void merge(int u, int v){
        u = leader(u);
        v = leader(v);
        if (u == v) return;
        p[v] = u;
    }
    bool same(int u, int v){
        return leader(u) == leader(v);
    }
}d(N);
int timer = 0;
void dfs(int u, int p){
    tin[u] = timer++;
    up[u][0] = p;
    for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : to[u]) {
        dfs(v, u);
    }
    tout[u] = timer;
}
bool is(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v){
    if (is(u, v)) return u;
    if (is(v, u)) return v;
    for (int i = 19; i >= 0; i--) {
        if (!is(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}
bool answer;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    ::n = n;
    ::m = m;
    std::vector<std::tuple<int, int, int>> edges;
    for (int i = 0; i < m; i++) {
        edges.emplace_back(W[i], U[i], V[i]);
    }
    sort(edges.begin(), edges.end());
    for (auto [w, u, v] : edges) {
        int nd = n++;
        ans[nd] = w;
        if (d.same(u, v)) {
            f[nd] = true;
            to[nd].push_back(d.leader(u));
            d.merge(nd, u);
        } else {
            to[nd].push_back(d.leader(u));
            to[nd].push_back(d.leader(v));
            d.merge(nd, u);
            d.merge(nd, v);
            f[nd] = f[d.leader(u)] | f[d.leader(v)] | (e[u].size() > 2 || e[v].size() > 2);
        }
        e[u].push_back(v);
        e[v].push_back(u);
    }
    assert(n == ::n + m);
    dfs(n - 1, n - 1);
    if (f[n - 1]) answer = true;
}
int getMinimumFuelCapacity(int X, int Y) {
    if (!answer) return -1;
    int l = lca(X, Y);
    while (!f[l]) l = up[l][0];
    return ans[l];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 11 ms 15520 KB Output is correct
3 Correct 13 ms 15532 KB Output is correct
4 Correct 11 ms 15692 KB Output is correct
5 Correct 12 ms 15816 KB Output is correct
6 Correct 12 ms 15860 KB Output is correct
7 Correct 12 ms 15864 KB Output is correct
8 Correct 12 ms 15840 KB Output is correct
9 Correct 138 ms 38932 KB Output is correct
10 Correct 179 ms 44192 KB Output is correct
11 Correct 166 ms 43756 KB Output is correct
12 Correct 182 ms 45392 KB Output is correct
13 Correct 152 ms 47800 KB Output is correct
14 Correct 139 ms 39352 KB Output is correct
15 Correct 242 ms 47728 KB Output is correct
16 Correct 223 ms 46796 KB Output is correct
17 Correct 235 ms 48576 KB Output is correct
18 Correct 217 ms 50864 KB Output is correct
19 Correct 121 ms 25164 KB Output is correct
20 Correct 296 ms 47392 KB Output is correct
21 Correct 276 ms 46688 KB Output is correct
22 Correct 330 ms 48536 KB Output is correct
23 Execution timed out 2008 ms 50384 KB Time limit exceeded

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 11 ms 15520 KB Output is correct
3 Correct 338 ms 52132 KB Output is correct
4 Correct 327 ms 53668 KB Output is correct
5 Correct 366 ms 53000 KB Output is correct
6 Correct 323 ms 53504 KB Output is correct
7 Incorrect 371 ms 53220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 11 ms 15520 KB Output is correct
3 Correct 13 ms 15532 KB Output is correct
4 Correct 11 ms 15692 KB Output is correct
5 Correct 12 ms 15816 KB Output is correct
6 Correct 12 ms 15860 KB Output is correct
7 Correct 12 ms 15864 KB Output is correct
8 Correct 12 ms 15840 KB Output is correct
9 Correct 11 ms 15564 KB Output is correct
10 Incorrect 12 ms 15820 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 11 ms 15564 KB Output is correct
3 Correct 11 ms 15520 KB Output is correct
4 Correct 13 ms 15532 KB Output is correct
5 Correct 11 ms 15692 KB Output is correct
6 Correct 12 ms 15816 KB Output is correct
7 Correct 12 ms 15860 KB Output is correct
8 Correct 12 ms 15864 KB Output is correct
9 Correct 12 ms 15840 KB Output is correct
10 Correct 138 ms 38932 KB Output is correct
11 Correct 179 ms 44192 KB Output is correct
12 Correct 166 ms 43756 KB Output is correct
13 Correct 182 ms 45392 KB Output is correct
14 Correct 152 ms 47800 KB Output is correct
15 Incorrect 12 ms 15820 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 11 ms 15520 KB Output is correct
3 Correct 13 ms 15532 KB Output is correct
4 Correct 11 ms 15692 KB Output is correct
5 Correct 12 ms 15816 KB Output is correct
6 Correct 12 ms 15860 KB Output is correct
7 Correct 12 ms 15864 KB Output is correct
8 Correct 12 ms 15840 KB Output is correct
9 Correct 138 ms 38932 KB Output is correct
10 Correct 179 ms 44192 KB Output is correct
11 Correct 166 ms 43756 KB Output is correct
12 Correct 182 ms 45392 KB Output is correct
13 Correct 152 ms 47800 KB Output is correct
14 Correct 139 ms 39352 KB Output is correct
15 Correct 242 ms 47728 KB Output is correct
16 Correct 223 ms 46796 KB Output is correct
17 Correct 235 ms 48576 KB Output is correct
18 Correct 217 ms 50864 KB Output is correct
19 Correct 338 ms 52132 KB Output is correct
20 Correct 327 ms 53668 KB Output is correct
21 Correct 366 ms 53000 KB Output is correct
22 Correct 323 ms 53504 KB Output is correct
23 Incorrect 371 ms 53220 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 11 ms 15564 KB Output is correct
3 Correct 11 ms 15520 KB Output is correct
4 Correct 13 ms 15532 KB Output is correct
5 Correct 11 ms 15692 KB Output is correct
6 Correct 12 ms 15816 KB Output is correct
7 Correct 12 ms 15860 KB Output is correct
8 Correct 12 ms 15864 KB Output is correct
9 Correct 12 ms 15840 KB Output is correct
10 Correct 138 ms 38932 KB Output is correct
11 Correct 179 ms 44192 KB Output is correct
12 Correct 166 ms 43756 KB Output is correct
13 Correct 182 ms 45392 KB Output is correct
14 Correct 152 ms 47800 KB Output is correct
15 Correct 139 ms 39352 KB Output is correct
16 Correct 242 ms 47728 KB Output is correct
17 Correct 223 ms 46796 KB Output is correct
18 Correct 235 ms 48576 KB Output is correct
19 Correct 217 ms 50864 KB Output is correct
20 Correct 338 ms 52132 KB Output is correct
21 Correct 327 ms 53668 KB Output is correct
22 Correct 366 ms 53000 KB Output is correct
23 Correct 323 ms 53504 KB Output is correct
24 Incorrect 371 ms 53220 KB Output isn't correct
25 Halted 0 ms 0 KB -