oj.uz

답안 #983554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983554 2024-05-15T17:33:48 Z RakhimovAmir 자매 도시 (APIO20_swap) C++14
0 / 100
 216 ms 44124 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e5 + 100, M = 30;
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];
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;
    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);
    }
    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++) {
        // 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 55 ms 36844 KB Output is correct
10 Correct 62 ms 38044 KB Output is correct
11 Correct 61 ms 38092 KB Output is correct
12 Correct 68 ms 38344 KB Output is correct
13 Correct 58 ms 38704 KB Output is correct
14 Correct 63 ms 36808 KB Output is correct
15 Correct 138 ms 40012 KB Output is correct
16 Correct 157 ms 39800 KB Output is correct
17 Correct 154 ms 40212 KB Output is correct
18 Correct 134 ms 40232 KB Output is correct
19 Incorrect 69 ms 19784 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Incorrect 216 ms 44124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Incorrect 3 ms 12380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12376 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 55 ms 36844 KB Output is correct
11 Correct 62 ms 38044 KB Output is correct
12 Correct 61 ms 38092 KB Output is correct
13 Correct 68 ms 38344 KB Output is correct
14 Correct 58 ms 38704 KB Output is correct
15 Incorrect 3 ms 12380 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 2 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12376 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 55 ms 36844 KB Output is correct
10 Correct 62 ms 38044 KB Output is correct
11 Correct 61 ms 38092 KB Output is correct
12 Correct 68 ms 38344 KB Output is correct
13 Correct 58 ms 38704 KB Output is correct
14 Correct 63 ms 36808 KB Output is correct
15 Correct 138 ms 40012 KB Output is correct
16 Correct 157 ms 39800 KB Output is correct
17 Correct 154 ms 40212 KB Output is correct
18 Correct 134 ms 40232 KB Output is correct
19 Incorrect 216 ms 44124 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12376 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 55 ms 36844 KB Output is correct
11 Correct 62 ms 38044 KB Output is correct
12 Correct 61 ms 38092 KB Output is correct
13 Correct 68 ms 38344 KB Output is correct
14 Correct 58 ms 38704 KB Output is correct
15 Correct 63 ms 36808 KB Output is correct
16 Correct 138 ms 40012 KB Output is correct
17 Correct 157 ms 39800 KB Output is correct
18 Correct 154 ms 40212 KB Output is correct
19 Correct 134 ms 40232 KB Output is correct
20 Incorrect 216 ms 44124 KB Output isn't correct
21 Halted 0 ms 0 KB -