oj.uz

답안 #983595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983595 2024-05-15T18:50:53 Z RakhimovAmir 자매 도시 (APIO20_swap) C++17
0 / 100
 142 ms 40240 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 = 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, 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;
        fl[Y] = 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 = 0; i <= G; 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 12124 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12120 KB Output is correct
5 Correct 3 ms 12376 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 53 ms 36900 KB Output is correct
10 Correct 62 ms 38092 KB Output is correct
11 Correct 62 ms 38080 KB Output is correct
12 Correct 68 ms 38344 KB Output is correct
13 Correct 72 ms 38600 KB Output is correct
14 Correct 68 ms 36912 KB Output is correct
15 Correct 137 ms 40008 KB Output is correct
16 Correct 141 ms 39800 KB Output is correct
17 Correct 142 ms 40240 KB Output is correct
18 Correct 136 ms 40104 KB Output is correct
19 Incorrect 78 ms 19800 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 12124 KB Output is correct
3 Runtime error 75 ms 37176 KB Execution killed with signal 11
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 12124 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12120 KB Output is correct
5 Correct 3 ms 12376 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Incorrect 3 ms 12268 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12120 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 12380 KB Output is correct
10 Correct 53 ms 36900 KB Output is correct
11 Correct 62 ms 38092 KB Output is correct
12 Correct 62 ms 38080 KB Output is correct
13 Correct 68 ms 38344 KB Output is correct
14 Correct 72 ms 38600 KB Output is correct
15 Incorrect 3 ms 12268 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 12124 KB Output is correct
3 Correct 2 ms 12120 KB Output is correct
4 Correct 3 ms 12120 KB Output is correct
5 Correct 3 ms 12376 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 53 ms 36900 KB Output is correct
10 Correct 62 ms 38092 KB Output is correct
11 Correct 62 ms 38080 KB Output is correct
12 Correct 68 ms 38344 KB Output is correct
13 Correct 72 ms 38600 KB Output is correct
14 Correct 68 ms 36912 KB Output is correct
15 Correct 137 ms 40008 KB Output is correct
16 Correct 141 ms 39800 KB Output is correct
17 Correct 142 ms 40240 KB Output is correct
18 Correct 136 ms 40104 KB Output is correct
19 Runtime error 75 ms 37176 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 2 ms 12124 KB Output is correct
4 Correct 2 ms 12120 KB Output is correct
5 Correct 3 ms 12120 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 12380 KB Output is correct
10 Correct 53 ms 36900 KB Output is correct
11 Correct 62 ms 38092 KB Output is correct
12 Correct 62 ms 38080 KB Output is correct
13 Correct 68 ms 38344 KB Output is correct
14 Correct 72 ms 38600 KB Output is correct
15 Correct 68 ms 36912 KB Output is correct
16 Correct 137 ms 40008 KB Output is correct
17 Correct 141 ms 39800 KB Output is correct
18 Correct 142 ms 40240 KB Output is correct
19 Correct 136 ms 40104 KB Output is correct
20 Runtime error 75 ms 37176 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -