oj.uz

Submission #983578

# Submission time Handle Problem Language Result Execution time Memory
983578 2024-05-15T18:32:19 Z RakhimovAmir Swapping Cities (APIO20_swap) C++17
0 / 100
 202 ms 44156 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

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;
        fl[Y] = 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 2 ms 12124 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12120 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 53 ms 36812 KB Output is correct
10 Correct 62 ms 38088 KB Output is correct
11 Correct 67 ms 37944 KB Output is correct
12 Correct 64 ms 38360 KB Output is correct
13 Correct 59 ms 38600 KB Output is correct
14 Correct 60 ms 36800 KB Output is correct
15 Correct 136 ms 39848 KB Output is correct
16 Correct 137 ms 39796 KB Output is correct
17 Correct 146 ms 40244 KB Output is correct
18 Correct 139 ms 40176 KB Output is correct
19 Incorrect 68 ms 19988 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12120 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 4 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 2 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 53 ms 36812 KB Output is correct
11 Correct 62 ms 38088 KB Output is correct
12 Correct 67 ms 37944 KB Output is correct
13 Correct 64 ms 38360 KB Output is correct
14 Correct 59 ms 38600 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 2 ms 12124 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12120 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 4 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 53 ms 36812 KB Output is correct
10 Correct 62 ms 38088 KB Output is correct
11 Correct 67 ms 37944 KB Output is correct
12 Correct 64 ms 38360 KB Output is correct
13 Correct 59 ms 38600 KB Output is correct
14 Correct 60 ms 36800 KB Output is correct
15 Correct 136 ms 39848 KB Output is correct
16 Correct 137 ms 39796 KB Output is correct
17 Correct 146 ms 40244 KB Output is correct
18 Correct 139 ms 40176 KB Output is correct
19 Incorrect 202 ms 44156 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 2 ms 12124 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 53 ms 36812 KB Output is correct
11 Correct 62 ms 38088 KB Output is correct
12 Correct 67 ms 37944 KB Output is correct
13 Correct 64 ms 38360 KB Output is correct
14 Correct 59 ms 38600 KB Output is correct
15 Correct 60 ms 36800 KB Output is correct
16 Correct 136 ms 39848 KB Output is correct
17 Correct 137 ms 39796 KB Output is correct
18 Correct 146 ms 40244 KB Output is correct
19 Correct 139 ms 40176 KB Output is correct
20 Incorrect 202 ms 44156 KB Output isn't correct
21 Halted 0 ms 0 KB -