oj.uz

Submission #983554

# Submission time Handle Problem Language Result Execution time Memory
983554 2024-05-15T17:33:48 Z RakhimovAmir Swapping Cities (APIO20_swap) C++14
0 / 100
 216 ms 44124 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

struct edge {
    int w, x, y;
};

const int N = 1e5 + 100, M = 30;
vector<pair<int, int>> g[N];
vector<edge> edges;
int prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt;
bool fl[N], visited[N];
vector<int> v[N];

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int findParent(int x) {
    if (prt[x] == x)
        return x;
    return prt[x] = findParent(prt[x]);
}

void addEdge(int x, int y, int w) {
    g[x].push_back({w, y});
    g[y].push_back({w, x});
}

void merge(int x, int y, int w) {
    int X = prt[x], Y = prt[y];
    if (X == Y) {
        if (!fl[X])
            return;
        fl[X] = 0;
        for (auto i : v[X]) {
            if (i != X) {
                addEdge(X, i, w);
            }
        }
        return;
    }
    if (v[Y].size() > v[X].size()) {
        swap(x, y);
        swap(X, Y);
    }
    for (auto i : v[Y]) {
        v[X].push_back(i);
    }
    prt[Y] = X;
    if (!fl[X] || !fl[Y] || (x != a[X] && x != b[X]) || (y != a[Y] && y != b[Y])) {
        fl[X] = 0;
        addEdge(X, Y, w);
        return;
    } else {
        if (x == a[X]) {
            if (y == b[Y])
                a[X] = a[Y];
            else
                a[X] = b[Y];
        }
        else {
            if (y == b[Y])
                b[X] = a[Y];
            else
                b[X] = b[Y];
        }
    }
}

void dfs(int x, int par, int w) {
    tin[x] = ++tt;
    visited[x] = 1;
    for (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    p[x][0] = par;
    mx[x][0] = w;
    for (int i = 1; i < M; i++) {
        p[x][i] = p[p[x][i - 1]][i - 1];
        mx[x][i] = max(mx[x][i - 1], mx[p[x][i - 1]][i - 1]);
        // cout << mx[x][i] << " " << x << " " << i << "\n";
    }
    tout[x] = tt;
}

int ispr(int x, int y) {
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y) {
    if (ispr(x, y))
        return x;
    if (ispr(y, x))
        return y;
    for (int i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y))
            x = p[x][i];
    }
    x = p[x][0];
    return x;
}

int findMax(int x, int y) {
    int ret = 0;
    if (x == y)
        return 0;
     for (int i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y)) {
            ret = max(ret, mx[x][i]);
            x = p[x][i];
        }
    }
    ret = max(ret, mx[x][0]);
    return ret;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < N; i++) {
        prt[i] = i;
        a[i] = i;
        b[i] = i;
        fl[i] = 1;
        v[i].push_back(i);
    }
    for (int i = 0; i < M; i++) {
        edges.push_back({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end(), cmp);
    for (auto i : edges) {
        merge(i.x, i.y, i.w);
    }

    for (int i = 0; i < N; i++) {
        // int pr = findParent(i);
        if (!visited[i]) {
            dfs(i, i, 0);
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int P = lca(X, Y);
    if (!ispr(P, X) || !ispr(P, Y) || X == Y)
      return -1;
    return max(findMax(X, P), findMax(Y, P));
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 55 ms 36844 KB Output is correct
10 Correct 62 ms 38044 KB Output is correct
11 Correct 61 ms 38092 KB Output is correct
12 Correct 68 ms 38344 KB Output is correct
13 Correct 58 ms 38704 KB Output is correct
14 Correct 63 ms 36808 KB Output is correct
15 Correct 138 ms 40012 KB Output is correct
16 Correct 157 ms 39800 KB Output is correct
17 Correct 154 ms 40212 KB Output is correct
18 Correct 134 ms 40232 KB Output is correct
19 Incorrect 69 ms 19784 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Incorrect 216 ms 44124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Incorrect 3 ms 12380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12376 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 55 ms 36844 KB Output is correct
11 Correct 62 ms 38044 KB Output is correct
12 Correct 61 ms 38092 KB Output is correct
13 Correct 68 ms 38344 KB Output is correct
14 Correct 58 ms 38704 KB Output is correct
15 Incorrect 3 ms 12380 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 55 ms 36844 KB Output is correct
10 Correct 62 ms 38044 KB Output is correct
11 Correct 61 ms 38092 KB Output is correct
12 Correct 68 ms 38344 KB Output is correct
13 Correct 58 ms 38704 KB Output is correct
14 Correct 63 ms 36808 KB Output is correct
15 Correct 138 ms 40012 KB Output is correct
16 Correct 157 ms 39800 KB Output is correct
17 Correct 154 ms 40212 KB Output is correct
18 Correct 134 ms 40232 KB Output is correct
19 Incorrect 216 ms 44124 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12376 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 55 ms 36844 KB Output is correct
11 Correct 62 ms 38044 KB Output is correct
12 Correct 61 ms 38092 KB Output is correct
13 Correct 68 ms 38344 KB Output is correct
14 Correct 58 ms 38704 KB Output is correct
15 Correct 63 ms 36808 KB Output is correct
16 Correct 138 ms 40012 KB Output is correct
17 Correct 157 ms 39800 KB Output is correct
18 Correct 154 ms 40212 KB Output is correct
19 Correct 134 ms 40232 KB Output is correct
20 Incorrect 216 ms 44124 KB Output isn't correct
21 Halted 0 ms 0 KB -