oj.uz

Submission #984414

# Submission time Handle Problem Language Result Execution time Memory
984414 2024-05-16T15:41:13 Z vjudge2 Swapping Cities (APIO20_swap) C++17
17 / 100
 2000 ms 54984 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
const int lg = 19;

int id, deg[N], ans[N], one[N], three[N], p[N], dep[N];
vector<int> adj[N];
vector<vector<int>> lift(N, vector<int> (lg));

int find(int u) {
    return p[u] == u ? u : find(p[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    p[v] = u;
    one[u] += one[v];
    three[u] += three[v];
}

void dfs(int u) {
    for (int v : adj[u]) {
        if (!ans[v]) ans[v] = ans[u];
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}

int jump(int s, int d) {
    for (int i = lg - 1; i >= 0; i--) if (d & (1 << i)) s = lift[s][i];
    return s;
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    v = jump(v, dep[v] - dep[u]);
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--) {
        int ut = lift[u][i], vt = lift[v][i];
        if (ut != vt) u = ut, v = vt;
    }
    return lift[u][0];
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    vector<array<int, 3>> e;
    for (int i = 0; i < m; i++) e.push_back({w[i], u[i], v[i]});
    sort(e.begin(), e.end());
    for (int i = 0; i < N; i++) p[i] = i;
    id = n - 1;
    for (auto& [w, u, v] : e) {
        int fu = find(u), fv = find(v);
        if (deg[u] == 1) one[fu]--;
        if (deg[v] == 1) one[fv]--;
        deg[u]++, deg[v]++;
        if (deg[u] == 1) one[fu]++;
        else if (deg[u] == 3) three[fu]++;
        if (deg[v] == 1) one[fv]++;
        else if (deg[v] == 3) three[fv]++;
        u = fu, v = fv;
        id++;
        if (u == v) {
            merge(id, u);
            lift[u][0] = id;
            adj[id].push_back(u);
            // cout << id << " --> " << u << '\n';
        } else {
            merge(id, u);
            merge(id, v);
            lift[u][0] = lift[v][0] = id;
            adj[id].push_back(u);
            // cout << id << " --> " << u << '\n';
            adj[id].push_back(v);
            // cout << id << " --> " << v << '\n';
        }
        if (three[id]) ans[id] = w;
        else if (!one[id]) ans[id] = w;
        // cout << "value @ " << id << " = " << w << '\n';
    }
    for (int i = 0; i < N; i++) if (find(i) == i) lift[i][0] = i, dfs(i);
    for (int j = 1; j < lg; j++) for (int i = 0; i < N; i++) {
        lift[i][j] = lift[lift[i][j - 1]][j - 1];
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    if (find(X) != find(Y)) return -1;
    // cout << lca(X, Y) << '\n';
    int l = lca(X, Y);
    if (ans[l] == 0) return -1;
    return ans[l];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 47964 KB Output is correct
2 Correct 66 ms 47976 KB Output is correct
3 Correct 66 ms 48084 KB Output is correct
4 Correct 66 ms 47964 KB Output is correct
5 Correct 63 ms 48216 KB Output is correct
6 Correct 67 ms 48220 KB Output is correct
7 Correct 70 ms 48140 KB Output is correct
8 Correct 66 ms 48220 KB Output is correct
9 Correct 131 ms 53448 KB Output is correct
10 Correct 143 ms 54732 KB Output is correct
11 Correct 150 ms 54640 KB Output is correct
12 Correct 150 ms 54984 KB Output is correct
13 Execution timed out 2049 ms 54984 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 47964 KB Output is correct
2 Correct 66 ms 47976 KB Output is correct
3 Execution timed out 2037 ms 54784 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 47964 KB Output is correct
2 Correct 66 ms 47976 KB Output is correct
3 Correct 66 ms 48084 KB Output is correct
4 Correct 66 ms 47964 KB Output is correct
5 Correct 63 ms 48216 KB Output is correct
6 Correct 67 ms 48220 KB Output is correct
7 Correct 70 ms 48140 KB Output is correct
8 Correct 66 ms 48220 KB Output is correct
9 Correct 77 ms 47960 KB Output is correct
10 Correct 73 ms 48156 KB Output is correct
11 Correct 66 ms 48220 KB Output is correct
12 Correct 66 ms 48220 KB Output is correct
13 Correct 82 ms 47952 KB Output is correct
14 Correct 69 ms 48220 KB Output is correct
15 Correct 70 ms 48220 KB Output is correct
16 Correct 65 ms 48220 KB Output is correct
17 Correct 67 ms 48216 KB Output is correct
18 Correct 69 ms 48168 KB Output is correct
19 Correct 67 ms 48216 KB Output is correct
20 Correct 67 ms 48216 KB Output is correct
21 Correct 67 ms 48220 KB Output is correct
22 Correct 72 ms 48416 KB Output is correct
23 Correct 67 ms 48220 KB Output is correct
24 Correct 73 ms 48216 KB Output is correct
25 Correct 69 ms 48208 KB Output is correct
26 Correct 74 ms 48220 KB Output is correct
27 Correct 64 ms 48224 KB Output is correct
28 Correct 75 ms 48216 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 47960 KB Output is correct
2 Correct 66 ms 47964 KB Output is correct
3 Correct 66 ms 47976 KB Output is correct
4 Correct 66 ms 48084 KB Output is correct
5 Correct 66 ms 47964 KB Output is correct
6 Correct 63 ms 48216 KB Output is correct
7 Correct 67 ms 48220 KB Output is correct
8 Correct 70 ms 48140 KB Output is correct
9 Correct 66 ms 48220 KB Output is correct
10 Correct 131 ms 53448 KB Output is correct
11 Correct 143 ms 54732 KB Output is correct
12 Correct 150 ms 54640 KB Output is correct
13 Correct 150 ms 54984 KB Output is correct
14 Execution timed out 2049 ms 54984 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 47964 KB Output is correct
2 Correct 66 ms 47976 KB Output is correct
3 Correct 66 ms 48084 KB Output is correct
4 Correct 66 ms 47964 KB Output is correct
5 Correct 63 ms 48216 KB Output is correct
6 Correct 67 ms 48220 KB Output is correct
7 Correct 70 ms 48140 KB Output is correct
8 Correct 66 ms 48220 KB Output is correct
9 Correct 131 ms 53448 KB Output is correct
10 Correct 143 ms 54732 KB Output is correct
11 Correct 150 ms 54640 KB Output is correct
12 Correct 150 ms 54984 KB Output is correct
13 Execution timed out 2049 ms 54984 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 47960 KB Output is correct
2 Correct 66 ms 47964 KB Output is correct
3 Correct 66 ms 47976 KB Output is correct
4 Correct 66 ms 48084 KB Output is correct
5 Correct 66 ms 47964 KB Output is correct
6 Correct 63 ms 48216 KB Output is correct
7 Correct 67 ms 48220 KB Output is correct
8 Correct 70 ms 48140 KB Output is correct
9 Correct 66 ms 48220 KB Output is correct
10 Correct 131 ms 53448 KB Output is correct
11 Correct 143 ms 54732 KB Output is correct
12 Correct 150 ms 54640 KB Output is correct
13 Correct 150 ms 54984 KB Output is correct
14 Execution timed out 2049 ms 54984 KB Time limit exceeded
15 Halted 0 ms 0 KB -