oj.uz

Submission #983608

# Submission time Handle Problem Language Result Execution time Memory
983608 2024-05-15T18:57:10 Z RakhimovAmir Swapping Cities (APIO20_swap) C++17
0 / 100
 155 ms 38836 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 (int(v[Y].size()) > int(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 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 3 ms 10472 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10428 KB Output is correct
9 Correct 50 ms 34248 KB Output is correct
10 Correct 70 ms 35440 KB Output is correct
11 Correct 60 ms 35264 KB Output is correct
12 Correct 65 ms 35788 KB Output is correct
13 Correct 58 ms 36044 KB Output is correct
14 Correct 61 ms 34504 KB Output is correct
15 Correct 126 ms 38228 KB Output is correct
16 Correct 126 ms 38256 KB Output is correct
17 Correct 155 ms 38704 KB Output is correct
18 Correct 122 ms 38836 KB Output is correct
19 Incorrect 62 ms 19324 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 10332 KB Output is correct
3 Runtime error 78 ms 35276 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 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 3 ms 10472 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10428 KB Output is correct
9 Incorrect 2 ms 10332 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 10332 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 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 3 ms 10472 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10428 KB Output is correct
9 Correct 50 ms 34248 KB Output is correct
10 Correct 70 ms 35440 KB Output is correct
11 Correct 60 ms 35264 KB Output is correct
12 Correct 65 ms 35788 KB Output is correct
13 Correct 58 ms 36044 KB Output is correct
14 Correct 61 ms 34504 KB Output is correct
15 Correct 126 ms 38228 KB Output is correct
16 Correct 126 ms 38256 KB Output is correct
17 Correct 155 ms 38704 KB Output is correct
18 Correct 122 ms 38836 KB Output is correct
19 Runtime error 78 ms 35276 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 10332 KB Output isn't correct
2 Halted 0 ms 0 KB -