oj.uz

답안 #981810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981810 2024-05-13T15:16:43 Z vjudge1 자매 도시 (APIO20_swap) C++17
0 / 100
 274 ms 50544 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 merge(int x, int y, int w) {
    int X = prt[x], Y = prt[y];
    if (X == Y) {
        fl[X] = 0;
        for (auto i : v[X]) {
            if (i != X && !is[{X, i}]) {
                g[X].push_back({w, i});
                g[i].push_back({w, X});
                is[{X, i}] = 1;
                is[{i, X}] = 1;
            }
        }
        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;
        g[X].push_back({w, Y});
        g[Y].push_back({w, X});
        is[{X, Y}] = 1;
        is[{Y, X}] = 1;
        return;
    } else {
        if (x == a[X])
            a[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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 10964 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 61 ms 33596 KB Output is correct
10 Correct 77 ms 35528 KB Output is correct
11 Correct 67 ms 35276 KB Output is correct
12 Correct 69 ms 36040 KB Output is correct
13 Correct 68 ms 36044 KB Output is correct
14 Correct 79 ms 34116 KB Output is correct
15 Incorrect 143 ms 39544 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 10964 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Incorrect 3 ms 11100 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 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 10964 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 61 ms 33596 KB Output is correct
11 Correct 77 ms 35528 KB Output is correct
12 Correct 67 ms 35276 KB Output is correct
13 Correct 69 ms 36040 KB Output is correct
14 Correct 68 ms 36044 KB Output is correct
15 Incorrect 3 ms 11100 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 10964 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 61 ms 33596 KB Output is correct
10 Correct 77 ms 35528 KB Output is correct
11 Correct 67 ms 35276 KB Output is correct
12 Correct 69 ms 36040 KB Output is correct
13 Correct 68 ms 36044 KB Output is correct
14 Correct 79 ms 34116 KB Output is correct
15 Incorrect 143 ms 39544 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 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 10964 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 61 ms 33596 KB Output is correct
11 Correct 77 ms 35528 KB Output is correct
12 Correct 67 ms 35276 KB Output is correct
13 Correct 69 ms 36040 KB Output is correct
14 Correct 68 ms 36044 KB Output is correct
15 Correct 79 ms 34116 KB Output is correct
16 Incorrect 143 ms 39544 KB Output isn't correct
17 Halted 0 ms 0 KB -