oj.uz

Submission #406448

# Submission time Handle Problem Language Result Execution time Memory
406448 2021-05-17T15:28:23 Z tengiz05 Swapping Cities (APIO20_swap) C++17
13 / 100
 361 ms 50216 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){
        return (u == p[u] ? u : p[u] = leader(p[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;
        e[u].push_back(v);
        e[v].push_back(u);
        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);
        }
    }
    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);
    if (f[l]) return ans[l];
    for (int i = 19; i >= 0; i--)
        if (!f[up[l][i]]) l = up[l][i];
    l = up[l][0];
    if(f[l]) return ans[l];
    return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 11 ms 15576 KB Output is correct
3 Correct 9 ms 15564 KB Output is correct
4 Correct 10 ms 15608 KB Output is correct
5 Correct 12 ms 15852 KB Output is correct
6 Correct 11 ms 15820 KB Output is correct
7 Correct 10 ms 15816 KB Output is correct
8 Correct 10 ms 15820 KB Output is correct
9 Correct 130 ms 37344 KB Output is correct
10 Correct 161 ms 42148 KB Output is correct
11 Correct 159 ms 41892 KB Output is correct
12 Correct 182 ms 43352 KB Output is correct
13 Correct 149 ms 45648 KB Output is correct
14 Correct 156 ms 37432 KB Output is correct
15 Correct 288 ms 43944 KB Output is correct
16 Correct 291 ms 43192 KB Output is correct
17 Correct 299 ms 45068 KB Output is correct
18 Correct 342 ms 47320 KB Output is correct
19 Correct 125 ms 23620 KB Output is correct
20 Correct 299 ms 45240 KB Output is correct
21 Correct 284 ms 44408 KB Output is correct
22 Correct 304 ms 46204 KB Output is correct
23 Correct 361 ms 48556 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 11 ms 15576 KB Output is correct
3 Correct 315 ms 48604 KB Output is correct
4 Correct 308 ms 50216 KB Output is correct
5 Correct 313 ms 49260 KB Output is correct
6 Correct 297 ms 49800 KB Output is correct
7 Correct 347 ms 49712 KB Output is correct
8 Correct 305 ms 48360 KB Output is correct
9 Correct 304 ms 49344 KB Output is correct
10 Correct 300 ms 47992 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 11 ms 15576 KB Output is correct
3 Correct 9 ms 15564 KB Output is correct
4 Correct 10 ms 15608 KB Output is correct
5 Correct 12 ms 15852 KB Output is correct
6 Correct 11 ms 15820 KB Output is correct
7 Correct 10 ms 15816 KB Output is correct
8 Correct 10 ms 15820 KB Output is correct
9 Correct 10 ms 15564 KB Output is correct
10 Correct 10 ms 15820 KB Output is correct
11 Incorrect 11 ms 15820 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15564 KB Output is correct
2 Correct 9 ms 15564 KB Output is correct
3 Correct 11 ms 15576 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 10 ms 15608 KB Output is correct
6 Correct 12 ms 15852 KB Output is correct
7 Correct 11 ms 15820 KB Output is correct
8 Correct 10 ms 15816 KB Output is correct
9 Correct 10 ms 15820 KB Output is correct
10 Correct 130 ms 37344 KB Output is correct
11 Correct 161 ms 42148 KB Output is correct
12 Correct 159 ms 41892 KB Output is correct
13 Correct 182 ms 43352 KB Output is correct
14 Correct 149 ms 45648 KB Output is correct
15 Correct 10 ms 15820 KB Output is correct
16 Incorrect 11 ms 15820 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 11 ms 15576 KB Output is correct
3 Correct 9 ms 15564 KB Output is correct
4 Correct 10 ms 15608 KB Output is correct
5 Correct 12 ms 15852 KB Output is correct
6 Correct 11 ms 15820 KB Output is correct
7 Correct 10 ms 15816 KB Output is correct
8 Correct 10 ms 15820 KB Output is correct
9 Correct 130 ms 37344 KB Output is correct
10 Correct 161 ms 42148 KB Output is correct
11 Correct 159 ms 41892 KB Output is correct
12 Correct 182 ms 43352 KB Output is correct
13 Correct 149 ms 45648 KB Output is correct
14 Correct 156 ms 37432 KB Output is correct
15 Correct 288 ms 43944 KB Output is correct
16 Correct 291 ms 43192 KB Output is correct
17 Correct 299 ms 45068 KB Output is correct
18 Correct 342 ms 47320 KB Output is correct
19 Correct 315 ms 48604 KB Output is correct
20 Correct 308 ms 50216 KB Output is correct
21 Correct 313 ms 49260 KB Output is correct
22 Correct 297 ms 49800 KB Output is correct
23 Correct 347 ms 49712 KB Output is correct
24 Correct 305 ms 48360 KB Output is correct
25 Correct 304 ms 49344 KB Output is correct
26 Correct 300 ms 47992 KB Output is correct
27 Correct 10 ms 15820 KB Output is correct
28 Incorrect 11 ms 15820 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15564 KB Output is correct
2 Correct 9 ms 15564 KB Output is correct
3 Correct 11 ms 15576 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 10 ms 15608 KB Output is correct
6 Correct 12 ms 15852 KB Output is correct
7 Correct 11 ms 15820 KB Output is correct
8 Correct 10 ms 15816 KB Output is correct
9 Correct 10 ms 15820 KB Output is correct
10 Correct 130 ms 37344 KB Output is correct
11 Correct 161 ms 42148 KB Output is correct
12 Correct 159 ms 41892 KB Output is correct
13 Correct 182 ms 43352 KB Output is correct
14 Correct 149 ms 45648 KB Output is correct
15 Correct 156 ms 37432 KB Output is correct
16 Correct 288 ms 43944 KB Output is correct
17 Correct 291 ms 43192 KB Output is correct
18 Correct 299 ms 45068 KB Output is correct
19 Correct 342 ms 47320 KB Output is correct
20 Correct 315 ms 48604 KB Output is correct
21 Correct 308 ms 50216 KB Output is correct
22 Correct 313 ms 49260 KB Output is correct
23 Correct 297 ms 49800 KB Output is correct
24 Correct 347 ms 49712 KB Output is correct
25 Correct 305 ms 48360 KB Output is correct
26 Correct 304 ms 49344 KB Output is correct
27 Correct 300 ms 47992 KB Output is correct
28 Correct 10 ms 15820 KB Output is correct
29 Incorrect 11 ms 15820 KB Output isn't correct
30 Halted 0 ms 0 KB -