oj.uz

Submission #406441

# Submission time Handle Problem Language Result Execution time Memory
406441 2021-05-17T15:24:47 Z tengiz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 50032 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;
        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]) 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 15564 KB Output is correct
3 Correct 9 ms 15564 KB Output is correct
4 Correct 10 ms 15692 KB Output is correct
5 Correct 10 ms 15820 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 10 ms 15820 KB Output is correct
8 Correct 12 ms 15848 KB Output is correct
9 Correct 133 ms 37356 KB Output is correct
10 Correct 161 ms 42376 KB Output is correct
11 Correct 175 ms 41752 KB Output is correct
12 Correct 186 ms 43320 KB Output is correct
13 Correct 162 ms 45644 KB Output is correct
14 Correct 150 ms 37460 KB Output is correct
15 Correct 317 ms 43932 KB Output is correct
16 Correct 287 ms 43172 KB Output is correct
17 Correct 288 ms 45040 KB Output is correct
18 Execution timed out 2079 ms 47296 KB Time limit exceeded

Subtask #2
0 / 7.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 321 ms 48608 KB Output is correct
4 Correct 308 ms 50032 KB Output is correct
5 Correct 311 ms 49264 KB Output is correct
6 Correct 328 ms 49800 KB Output is correct
7 Incorrect 317 ms 49580 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 17.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 15564 KB Output is correct
4 Correct 10 ms 15692 KB Output is correct
5 Correct 10 ms 15820 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 10 ms 15820 KB Output is correct
8 Correct 12 ms 15848 KB Output is correct
9 Correct 10 ms 15564 KB Output is correct
10 Incorrect 11 ms 15756 KB Output isn't correct
11 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 9 ms 15564 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 10 ms 15692 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 10 ms 15820 KB Output is correct
8 Correct 10 ms 15820 KB Output is correct
9 Correct 12 ms 15848 KB Output is correct
10 Correct 133 ms 37356 KB Output is correct
11 Correct 161 ms 42376 KB Output is correct
12 Correct 175 ms 41752 KB Output is correct
13 Correct 186 ms 43320 KB Output is correct
14 Correct 162 ms 45644 KB Output is correct
15 Incorrect 11 ms 15756 KB Output isn't correct
16 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 15564 KB Output is correct
3 Correct 9 ms 15564 KB Output is correct
4 Correct 10 ms 15692 KB Output is correct
5 Correct 10 ms 15820 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 10 ms 15820 KB Output is correct
8 Correct 12 ms 15848 KB Output is correct
9 Correct 133 ms 37356 KB Output is correct
10 Correct 161 ms 42376 KB Output is correct
11 Correct 175 ms 41752 KB Output is correct
12 Correct 186 ms 43320 KB Output is correct
13 Correct 162 ms 45644 KB Output is correct
14 Correct 150 ms 37460 KB Output is correct
15 Correct 317 ms 43932 KB Output is correct
16 Correct 287 ms 43172 KB Output is correct
17 Correct 288 ms 45040 KB Output is correct
18 Execution timed out 2079 ms 47296 KB Time limit exceeded

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 9 ms 15564 KB Output is correct
4 Correct 9 ms 15564 KB Output is correct
5 Correct 10 ms 15692 KB Output is correct
6 Correct 10 ms 15820 KB Output is correct
7 Correct 10 ms 15820 KB Output is correct
8 Correct 10 ms 15820 KB Output is correct
9 Correct 12 ms 15848 KB Output is correct
10 Correct 133 ms 37356 KB Output is correct
11 Correct 161 ms 42376 KB Output is correct
12 Correct 175 ms 41752 KB Output is correct
13 Correct 186 ms 43320 KB Output is correct
14 Correct 162 ms 45644 KB Output is correct
15 Correct 150 ms 37460 KB Output is correct
16 Correct 317 ms 43932 KB Output is correct
17 Correct 287 ms 43172 KB Output is correct
18 Correct 288 ms 45040 KB Output is correct
19 Execution timed out 2079 ms 47296 KB Time limit exceeded