oj.uz

Submission #983603

# Submission time Handle Problem Language Result Execution time Memory
983603 2024-05-15T18:54:15 Z RakhimovAmir Swapping Cities (APIO20_swap) C++17
0 / 100
 131 ms 36328 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct edge {
    int w, x, y;
};

const int N = 1e5 + 100, M = 25;
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, G;
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;
        G++;
        for (auto i : v[X]) {
            addEdge(G, i, w);
        }
        v[X].clear();
        v[X].push_back(G);
        return;
    }
    if (v[Y].size() > v[X].size()) {
        swap(x, y);
        swap(X, Y);
    }
    prt[Y] = X;
    for (auto i : v[Y]) {
        v[X].push_back(i);
    }
    if (!fl[X] || !fl[Y] || (x != a[X] && x != b[X]) || (y != a[Y] && y != b[Y])) {
        fl[X] = 0;
        G++;
        for (auto i : v[X]) {
            addEdge(G, i, w);
        }
        v[X].clear();
        v[X].push_back(G);
        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;
    for (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    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]);
        // 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);
    }
    G = N - 1;
    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 = G; i >= 0; 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 10332 KB Output is correct
2 Correct 2 ms 10468 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 3 ms 10332 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 50 ms 32964 KB Output is correct
10 Correct 62 ms 34244 KB Output is correct
11 Correct 60 ms 34036 KB Output is correct
12 Correct 64 ms 34544 KB Output is correct
13 Correct 58 ms 34764 KB Output is correct
14 Correct 57 ms 32968 KB Output is correct
15 Correct 131 ms 36328 KB Output is correct
16 Correct 126 ms 35956 KB Output is correct
17 Correct 125 ms 36144 KB Output is correct
18 Correct 122 ms 36224 KB Output is correct
19 Incorrect 59 ms 18072 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 10332 KB Output is correct
2 Correct 2 ms 10468 KB Output is correct
3 Runtime error 74 ms 33416 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10468 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 3 ms 10332 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Incorrect 2 ms 10584 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10468 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 3 ms 10332 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 50 ms 32964 KB Output is correct
10 Correct 62 ms 34244 KB Output is correct
11 Correct 60 ms 34036 KB Output is correct
12 Correct 64 ms 34544 KB Output is correct
13 Correct 58 ms 34764 KB Output is correct
14 Correct 57 ms 32968 KB Output is correct
15 Correct 131 ms 36328 KB Output is correct
16 Correct 126 ms 35956 KB Output is correct
17 Correct 125 ms 36144 KB Output is correct
18 Correct 122 ms 36224 KB Output is correct
19 Runtime error 74 ms 33416 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -