oj.uz

Submission #981834

# Submission time Handle Problem Language Result Execution time Memory
981834 2024-05-13T15:31:08 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 285 ms 50540 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) {
        if (!fl[X])
            return;
        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]) {
            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))
      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 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11036 KB Output is correct
9 Correct 59 ms 31404 KB Output is correct
10 Correct 60 ms 32716 KB Output is correct
11 Correct 58 ms 32460 KB Output is correct
12 Correct 63 ms 32968 KB Output is correct
13 Correct 62 ms 33244 KB Output is correct
14 Correct 57 ms 31344 KB Output is correct
15 Correct 130 ms 34392 KB Output is correct
16 Correct 138 ms 38828 KB Output is correct
17 Correct 152 ms 39064 KB Output is correct
18 Correct 149 ms 39160 KB Output is correct
19 Incorrect 65 ms 20416 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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Incorrect 285 ms 50540 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 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11036 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 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 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 11036 KB Output is correct
10 Correct 59 ms 31404 KB Output is correct
11 Correct 60 ms 32716 KB Output is correct
12 Correct 58 ms 32460 KB Output is correct
13 Correct 63 ms 32968 KB Output is correct
14 Correct 62 ms 33244 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 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 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11036 KB Output is correct
9 Correct 59 ms 31404 KB Output is correct
10 Correct 60 ms 32716 KB Output is correct
11 Correct 58 ms 32460 KB Output is correct
12 Correct 63 ms 32968 KB Output is correct
13 Correct 62 ms 33244 KB Output is correct
14 Correct 57 ms 31344 KB Output is correct
15 Correct 130 ms 34392 KB Output is correct
16 Correct 138 ms 38828 KB Output is correct
17 Correct 152 ms 39064 KB Output is correct
18 Correct 149 ms 39160 KB Output is correct
19 Incorrect 285 ms 50540 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 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 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 11036 KB Output is correct
10 Correct 59 ms 31404 KB Output is correct
11 Correct 60 ms 32716 KB Output is correct
12 Correct 58 ms 32460 KB Output is correct
13 Correct 63 ms 32968 KB Output is correct
14 Correct 62 ms 33244 KB Output is correct
15 Correct 57 ms 31344 KB Output is correct
16 Correct 130 ms 34392 KB Output is correct
17 Correct 138 ms 38828 KB Output is correct
18 Correct 152 ms 39064 KB Output is correct
19 Correct 149 ms 39160 KB Output is correct
20 Incorrect 285 ms 50540 KB Output isn't correct
21 Halted 0 ms 0 KB -