oj.uz

Submission #406439

# Submission time Handle Problem Language Result Execution time Memory
406439 2021-05-17T15:20:26 Z tengiz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 50740 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]) 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 11 ms 15580 KB Output is correct
2 Correct 11 ms 15568 KB Output is correct
3 Correct 11 ms 15496 KB Output is correct
4 Correct 13 ms 15676 KB Output is correct
5 Correct 13 ms 15804 KB Output is correct
6 Correct 12 ms 15804 KB Output is correct
7 Correct 13 ms 15828 KB Output is correct
8 Correct 12 ms 15820 KB Output is correct
9 Correct 134 ms 37716 KB Output is correct
10 Correct 172 ms 42624 KB Output is correct
11 Correct 197 ms 42168 KB Output is correct
12 Correct 177 ms 43732 KB Output is correct
13 Correct 154 ms 46092 KB Output is correct
14 Correct 145 ms 37972 KB Output is correct
15 Correct 287 ms 44948 KB Output is correct
16 Correct 274 ms 44236 KB Output is correct
17 Correct 297 ms 45924 KB Output is correct
18 Execution timed out 2036 ms 48116 KB Time limit exceeded

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15580 KB Output is correct
2 Correct 11 ms 15568 KB Output is correct
3 Correct 313 ms 49172 KB Output is correct
4 Correct 323 ms 50740 KB Output is correct
5 Correct 351 ms 49896 KB Output is correct
6 Correct 326 ms 50452 KB Output is correct
7 Incorrect 339 ms 50356 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 15580 KB Output is correct
2 Correct 11 ms 15568 KB Output is correct
3 Correct 11 ms 15496 KB Output is correct
4 Correct 13 ms 15676 KB Output is correct
5 Correct 13 ms 15804 KB Output is correct
6 Correct 12 ms 15804 KB Output is correct
7 Correct 13 ms 15828 KB Output is correct
8 Correct 12 ms 15820 KB Output is correct
9 Correct 11 ms 15516 KB Output is correct
10 Incorrect 12 ms 15836 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 15516 KB Output is correct
2 Correct 11 ms 15580 KB Output is correct
3 Correct 11 ms 15568 KB Output is correct
4 Correct 11 ms 15496 KB Output is correct
5 Correct 13 ms 15676 KB Output is correct
6 Correct 13 ms 15804 KB Output is correct
7 Correct 12 ms 15804 KB Output is correct
8 Correct 13 ms 15828 KB Output is correct
9 Correct 12 ms 15820 KB Output is correct
10 Correct 134 ms 37716 KB Output is correct
11 Correct 172 ms 42624 KB Output is correct
12 Correct 197 ms 42168 KB Output is correct
13 Correct 177 ms 43732 KB Output is correct
14 Correct 154 ms 46092 KB Output is correct
15 Incorrect 12 ms 15836 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 15580 KB Output is correct
2 Correct 11 ms 15568 KB Output is correct
3 Correct 11 ms 15496 KB Output is correct
4 Correct 13 ms 15676 KB Output is correct
5 Correct 13 ms 15804 KB Output is correct
6 Correct 12 ms 15804 KB Output is correct
7 Correct 13 ms 15828 KB Output is correct
8 Correct 12 ms 15820 KB Output is correct
9 Correct 134 ms 37716 KB Output is correct
10 Correct 172 ms 42624 KB Output is correct
11 Correct 197 ms 42168 KB Output is correct
12 Correct 177 ms 43732 KB Output is correct
13 Correct 154 ms 46092 KB Output is correct
14 Correct 145 ms 37972 KB Output is correct
15 Correct 287 ms 44948 KB Output is correct
16 Correct 274 ms 44236 KB Output is correct
17 Correct 297 ms 45924 KB Output is correct
18 Execution timed out 2036 ms 48116 KB Time limit exceeded

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15516 KB Output is correct
2 Correct 11 ms 15580 KB Output is correct
3 Correct 11 ms 15568 KB Output is correct
4 Correct 11 ms 15496 KB Output is correct
5 Correct 13 ms 15676 KB Output is correct
6 Correct 13 ms 15804 KB Output is correct
7 Correct 12 ms 15804 KB Output is correct
8 Correct 13 ms 15828 KB Output is correct
9 Correct 12 ms 15820 KB Output is correct
10 Correct 134 ms 37716 KB Output is correct
11 Correct 172 ms 42624 KB Output is correct
12 Correct 197 ms 42168 KB Output is correct
13 Correct 177 ms 43732 KB Output is correct
14 Correct 154 ms 46092 KB Output is correct
15 Correct 145 ms 37972 KB Output is correct
16 Correct 287 ms 44948 KB Output is correct
17 Correct 274 ms 44236 KB Output is correct
18 Correct 297 ms 45924 KB Output is correct
19 Execution timed out 2036 ms 48116 KB Time limit exceeded