oj.uz

Submission #983547

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

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

const int N = 1e5 + 100, M = 23;
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];
map<pair<int, int>, bool> is;
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;
    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]);
    }
    for (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    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++) {
        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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 50 ms 31180 KB Output is correct
10 Correct 58 ms 32548 KB Output is correct
11 Correct 57 ms 32456 KB Output is correct
12 Correct 63 ms 32944 KB Output is correct
13 Correct 55 ms 33224 KB Output is correct
14 Correct 58 ms 31688 KB Output is correct
15 Correct 133 ms 34380 KB Output is correct
16 Correct 147 ms 34424 KB Output is correct
17 Correct 130 ms 34652 KB Output is correct
18 Correct 134 ms 34816 KB Output is correct
19 Incorrect 75 ms 18428 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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Incorrect 176 ms 38676 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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Incorrect 2 ms 10844 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 50 ms 31180 KB Output is correct
11 Correct 58 ms 32548 KB Output is correct
12 Correct 57 ms 32456 KB Output is correct
13 Correct 63 ms 32944 KB Output is correct
14 Correct 55 ms 33224 KB Output is correct
15 Incorrect 2 ms 10844 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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 50 ms 31180 KB Output is correct
10 Correct 58 ms 32548 KB Output is correct
11 Correct 57 ms 32456 KB Output is correct
12 Correct 63 ms 32944 KB Output is correct
13 Correct 55 ms 33224 KB Output is correct
14 Correct 58 ms 31688 KB Output is correct
15 Correct 133 ms 34380 KB Output is correct
16 Correct 147 ms 34424 KB Output is correct
17 Correct 130 ms 34652 KB Output is correct
18 Correct 134 ms 34816 KB Output is correct
19 Incorrect 176 ms 38676 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 50 ms 31180 KB Output is correct
11 Correct 58 ms 32548 KB Output is correct
12 Correct 57 ms 32456 KB Output is correct
13 Correct 63 ms 32944 KB Output is correct
14 Correct 55 ms 33224 KB Output is correct
15 Correct 58 ms 31688 KB Output is correct
16 Correct 133 ms 34380 KB Output is correct
17 Correct 147 ms 34424 KB Output is correct
18 Correct 130 ms 34652 KB Output is correct
19 Correct 134 ms 34816 KB Output is correct
20 Incorrect 176 ms 38676 KB Output isn't correct
21 Halted 0 ms 0 KB -