oj.uz

Submission #983545

# Submission time Handle Problem Language Result Execution time Memory
983545 2024-05-15T17:01:31 Z vjudge1 Swapping Cities (APIO20_swap) C++17
0 / 100
 195 ms 42620 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))
      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 11000 KB Output is correct
7 Correct 3 ms 10964 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 50 ms 33064 KB Output is correct
10 Correct 60 ms 34788 KB Output is correct
11 Correct 58 ms 34504 KB Output is correct
12 Correct 63 ms 34936 KB Output is correct
13 Correct 65 ms 35276 KB Output is correct
14 Correct 55 ms 33220 KB Output is correct
15 Correct 130 ms 38732 KB Output is correct
16 Correct 132 ms 38460 KB Output is correct
17 Correct 132 ms 39232 KB Output is correct
18 Correct 127 ms 39216 KB Output is correct
19 Incorrect 67 ms 20392 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 195 ms 42620 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 11000 KB Output is correct
7 Correct 3 ms 10964 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Incorrect 3 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 11000 KB Output is correct
8 Correct 3 ms 10964 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 50 ms 33064 KB Output is correct
11 Correct 60 ms 34788 KB Output is correct
12 Correct 58 ms 34504 KB Output is correct
13 Correct 63 ms 34936 KB Output is correct
14 Correct 65 ms 35276 KB Output is correct
15 Incorrect 3 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 11000 KB Output is correct
7 Correct 3 ms 10964 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 50 ms 33064 KB Output is correct
10 Correct 60 ms 34788 KB Output is correct
11 Correct 58 ms 34504 KB Output is correct
12 Correct 63 ms 34936 KB Output is correct
13 Correct 65 ms 35276 KB Output is correct
14 Correct 55 ms 33220 KB Output is correct
15 Correct 130 ms 38732 KB Output is correct
16 Correct 132 ms 38460 KB Output is correct
17 Correct 132 ms 39232 KB Output is correct
18 Correct 127 ms 39216 KB Output is correct
19 Incorrect 195 ms 42620 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 11000 KB Output is correct
8 Correct 3 ms 10964 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 50 ms 33064 KB Output is correct
11 Correct 60 ms 34788 KB Output is correct
12 Correct 58 ms 34504 KB Output is correct
13 Correct 63 ms 34936 KB Output is correct
14 Correct 65 ms 35276 KB Output is correct
15 Correct 55 ms 33220 KB Output is correct
16 Correct 130 ms 38732 KB Output is correct
17 Correct 132 ms 38460 KB Output is correct
18 Correct 132 ms 39232 KB Output is correct
19 Correct 127 ms 39216 KB Output is correct
20 Incorrect 195 ms 42620 KB Output isn't correct
21 Halted 0 ms 0 KB -