oj.uz

Submission #406445

# Submission time Handle Problem Language Result Execution time Memory
406445 2021-05-17T15:26:42 Z tengiz05 Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 53172 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);
    while (!f[l] && l != up[l][0]) l = up[l][0];
    if(f[l]) return ans[l];
    return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15612 KB Output is correct
3 Correct 9 ms 15552 KB Output is correct
4 Correct 9 ms 15704 KB Output is correct
5 Correct 10 ms 15820 KB Output is correct
6 Correct 11 ms 15820 KB Output is correct
7 Correct 11 ms 15844 KB Output is correct
8 Correct 11 ms 15820 KB Output is correct
9 Correct 126 ms 37408 KB Output is correct
10 Correct 159 ms 42344 KB Output is correct
11 Correct 161 ms 41816 KB Output is correct
12 Correct 165 ms 43332 KB Output is correct
13 Correct 146 ms 45664 KB Output is correct
14 Correct 140 ms 37404 KB Output is correct
15 Correct 319 ms 43960 KB Output is correct
16 Correct 277 ms 43176 KB Output is correct
17 Correct 273 ms 44916 KB Output is correct
18 Execution timed out 2086 ms 47196 KB Time limit exceeded

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15612 KB Output is correct
3 Correct 302 ms 48480 KB Output is correct
4 Correct 309 ms 50052 KB Output is correct
5 Correct 317 ms 49196 KB Output is correct
6 Correct 312 ms 49836 KB Output is correct
7 Correct 311 ms 49652 KB Output is correct
8 Correct 302 ms 52116 KB Output is correct
9 Correct 302 ms 53172 KB Output is correct
10 Correct 294 ms 51884 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 9 ms 15612 KB Output is correct
3 Correct 9 ms 15552 KB Output is correct
4 Correct 9 ms 15704 KB Output is correct
5 Correct 10 ms 15820 KB Output is correct
6 Correct 11 ms 15820 KB Output is correct
7 Correct 11 ms 15844 KB Output is correct
8 Correct 11 ms 15820 KB Output is correct
9 Correct 9 ms 15564 KB Output is correct
10 Correct 10 ms 15820 KB Output is correct
11 Incorrect 10 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 9 ms 15564 KB Output is correct
2 Correct 9 ms 15564 KB Output is correct
3 Correct 9 ms 15612 KB Output is correct
4 Correct 9 ms 15552 KB Output is correct
5 Correct 9 ms 15704 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 11 ms 15820 KB Output is correct
8 Correct 11 ms 15844 KB Output is correct
9 Correct 11 ms 15820 KB Output is correct
10 Correct 126 ms 37408 KB Output is correct
11 Correct 159 ms 42344 KB Output is correct
12 Correct 161 ms 41816 KB Output is correct
13 Correct 165 ms 43332 KB Output is correct
14 Correct 146 ms 45664 KB Output is correct
15 Correct 10 ms 15820 KB Output is correct
16 Incorrect 10 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 9 ms 15612 KB Output is correct
3 Correct 9 ms 15552 KB Output is correct
4 Correct 9 ms 15704 KB Output is correct
5 Correct 10 ms 15820 KB Output is correct
6 Correct 11 ms 15820 KB Output is correct
7 Correct 11 ms 15844 KB Output is correct
8 Correct 11 ms 15820 KB Output is correct
9 Correct 126 ms 37408 KB Output is correct
10 Correct 159 ms 42344 KB Output is correct
11 Correct 161 ms 41816 KB Output is correct
12 Correct 165 ms 43332 KB Output is correct
13 Correct 146 ms 45664 KB Output is correct
14 Correct 140 ms 37404 KB Output is correct
15 Correct 319 ms 43960 KB Output is correct
16 Correct 277 ms 43176 KB Output is correct
17 Correct 273 ms 44916 KB Output is correct
18 Execution timed out 2086 ms 47196 KB Time limit exceeded

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15564 KB Output is correct
3 Correct 9 ms 15612 KB Output is correct
4 Correct 9 ms 15552 KB Output is correct
5 Correct 9 ms 15704 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 11 ms 15820 KB Output is correct
8 Correct 11 ms 15844 KB Output is correct
9 Correct 11 ms 15820 KB Output is correct
10 Correct 126 ms 37408 KB Output is correct
11 Correct 159 ms 42344 KB Output is correct
12 Correct 161 ms 41816 KB Output is correct
13 Correct 165 ms 43332 KB Output is correct
14 Correct 146 ms 45664 KB Output is correct
15 Correct 140 ms 37404 KB Output is correct
16 Correct 319 ms 43960 KB Output is correct
17 Correct 277 ms 43176 KB Output is correct
18 Correct 273 ms 44916 KB Output is correct
19 Execution timed out 2086 ms 47196 KB Time limit exceeded