oj.uz

Submission #981815

# Submission time Handle Problem Language Result Execution time Memory
981815 2024-05-13T15:19:44 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 270 ms 50460 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])
            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 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 67 ms 32160 KB Output is correct
10 Correct 66 ms 33360 KB Output is correct
11 Correct 75 ms 33492 KB Output is correct
12 Correct 71 ms 33752 KB Output is correct
13 Correct 60 ms 33480 KB Output is correct
14 Correct 70 ms 32052 KB Output is correct
15 Incorrect 144 ms 35408 KB Output isn't correct
16 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 270 ms 50460 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 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 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 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 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 67 ms 32160 KB Output is correct
11 Correct 66 ms 33360 KB Output is correct
12 Correct 75 ms 33492 KB Output is correct
13 Correct 71 ms 33752 KB Output is correct
14 Correct 60 ms 33480 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 3 ms 10840 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 67 ms 32160 KB Output is correct
10 Correct 66 ms 33360 KB Output is correct
11 Correct 75 ms 33492 KB Output is correct
12 Correct 71 ms 33752 KB Output is correct
13 Correct 60 ms 33480 KB Output is correct
14 Correct 70 ms 32052 KB Output is correct
15 Incorrect 144 ms 35408 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 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 67 ms 32160 KB Output is correct
11 Correct 66 ms 33360 KB Output is correct
12 Correct 75 ms 33492 KB Output is correct
13 Correct 71 ms 33752 KB Output is correct
14 Correct 60 ms 33480 KB Output is correct
15 Correct 70 ms 32052 KB Output is correct
16 Incorrect 144 ms 35408 KB Output isn't correct
17 Halted 0 ms 0 KB -