oj.uz

Submission #981810

# Submission time Handle Problem Language Result Execution time Memory
981810 2024-05-13T15:16:43 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 274 ms 50544 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 merge(int x, int y, int w) {
    int X = prt[x], Y = prt[y];
    if (X == Y) {
        fl[X] = 0;
        for (auto i : v[X]) {
            if (i != X && !is[{X, i}]) {
                g[X].push_back({w, i});
                g[i].push_back({w, X});
                is[{X, i}] = 1;
                is[{i, X}] = 1;
            }
        }
        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;
        g[X].push_back({w, Y});
        g[Y].push_back({w, X});
        is[{X, Y}] = 1;
        is[{Y, X}] = 1;
        return;
    } else {
        if (x == a[X])
            a[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))
      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 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 10964 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 61 ms 33596 KB Output is correct
10 Correct 77 ms 35528 KB Output is correct
11 Correct 67 ms 35276 KB Output is correct
12 Correct 69 ms 36040 KB Output is correct
13 Correct 68 ms 36044 KB Output is correct
14 Correct 79 ms 34116 KB Output is correct
15 Incorrect 143 ms 39544 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Incorrect 274 ms 50544 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 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 10964 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Incorrect 3 ms 11100 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 3 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 10964 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 61 ms 33596 KB Output is correct
11 Correct 77 ms 35528 KB Output is correct
12 Correct 67 ms 35276 KB Output is correct
13 Correct 69 ms 36040 KB Output is correct
14 Correct 68 ms 36044 KB Output is correct
15 Incorrect 3 ms 11100 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 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 10964 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 61 ms 33596 KB Output is correct
10 Correct 77 ms 35528 KB Output is correct
11 Correct 67 ms 35276 KB Output is correct
12 Correct 69 ms 36040 KB Output is correct
13 Correct 68 ms 36044 KB Output is correct
14 Correct 79 ms 34116 KB Output is correct
15 Incorrect 143 ms 39544 KB Output isn't correct
16 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 3 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 10964 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 61 ms 33596 KB Output is correct
11 Correct 77 ms 35528 KB Output is correct
12 Correct 67 ms 35276 KB Output is correct
13 Correct 69 ms 36040 KB Output is correct
14 Correct 68 ms 36044 KB Output is correct
15 Correct 79 ms 34116 KB Output is correct
16 Incorrect 143 ms 39544 KB Output isn't correct
17 Halted 0 ms 0 KB -