oj.uz

Submission #983553

# Submission time Handle Problem Language Result Execution time Memory
983553 2024-05-15T17:32:34 Z RakhimovAmir Swapping Cities (APIO20_swap) C++14
0 / 100
 181 ms 38608 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];
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 (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10928 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 48 ms 31156 KB Output is correct
10 Correct 59 ms 32748 KB Output is correct
11 Correct 60 ms 32476 KB Output is correct
12 Correct 74 ms 32992 KB Output is correct
13 Correct 56 ms 33240 KB Output is correct
14 Correct 59 ms 31532 KB Output is correct
15 Correct 130 ms 34496 KB Output is correct
16 Correct 134 ms 34396 KB Output is correct
17 Correct 139 ms 34604 KB Output is correct
18 Correct 127 ms 34612 KB Output is correct
19 Incorrect 70 ms 18448 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Incorrect 181 ms 38608 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10928 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Incorrect 2 ms 10840 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 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10928 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 48 ms 31156 KB Output is correct
11 Correct 59 ms 32748 KB Output is correct
12 Correct 60 ms 32476 KB Output is correct
13 Correct 74 ms 32992 KB Output is correct
14 Correct 56 ms 33240 KB Output is correct
15 Incorrect 2 ms 10840 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 3 ms 10928 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 48 ms 31156 KB Output is correct
10 Correct 59 ms 32748 KB Output is correct
11 Correct 60 ms 32476 KB Output is correct
12 Correct 74 ms 32992 KB Output is correct
13 Correct 56 ms 33240 KB Output is correct
14 Correct 59 ms 31532 KB Output is correct
15 Correct 130 ms 34496 KB Output is correct
16 Correct 134 ms 34396 KB Output is correct
17 Correct 139 ms 34604 KB Output is correct
18 Correct 127 ms 34612 KB Output is correct
19 Incorrect 181 ms 38608 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 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10928 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 48 ms 31156 KB Output is correct
11 Correct 59 ms 32748 KB Output is correct
12 Correct 60 ms 32476 KB Output is correct
13 Correct 74 ms 32992 KB Output is correct
14 Correct 56 ms 33240 KB Output is correct
15 Correct 59 ms 31532 KB Output is correct
16 Correct 130 ms 34496 KB Output is correct
17 Correct 134 ms 34396 KB Output is correct
18 Correct 139 ms 34604 KB Output is correct
19 Correct 127 ms 34612 KB Output is correct
20 Incorrect 181 ms 38608 KB Output isn't correct
21 Halted 0 ms 0 KB -