oj.uz

답안 #714940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714940 2023-03-25T14:30:00 Z dxz05 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 209472 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 100005;
vector<tuple<int, int, int>> edges;

int N, M;
const int blockLength = 800;

struct Set{
    int parent;
    bool line;
    pair<int, int> tail;
    Set(){};
    Set(int i){
        parent = i;
        line = true;
        tail = make_pair(i, i);
    }
};

Set t[MaxN];

int MAGIC;
bool flag[MaxN];
Set mem[MaxN][MaxN / blockLength + 4];

vector<int> re;

int leader(int x){
    if (MAGIC != -1 && !flag[x]){
        t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
        flag[x] = true;
        re.push_back(x);
    }
    return t[x].parent == x ? x : t[x].parent = leader(t[x].parent);
}

void unite(int x, int y){
    int X = x, Y = y;
    x = leader(x);
    y = leader(y);

    if (x == y){
        t[y].line = false;
        return;
    }

    t[x].parent = y;
    if (!t[x].line){
        t[y].line = false;
        return;
    }

    if (!t[y].line) return;

    if (t[x].tail.first != X && t[x].tail.second != X){
        t[y].line = false;
        return;
    }

    if (t[y].tail.first != Y && t[y].tail.second != Y){
        t[y].line = false;
        return;
    }

    pair<int, int> new_tail;
    new_tail.first = t[x].tail.first ^ t[x].tail.second ^ X;
    new_tail.second = t[y].tail.first ^ t[y].tail.second ^ Y;

    t[y].tail = new_tail;
}

int el[MaxN], er[MaxN];

int blockCount;
void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    N = _N, M = _M;

    for (int i = 0; i < M; i++){
        edges.emplace_back(W[i], U[i], V[i]);
    }

    sort(edges.begin(), edges.end());

    for (int i = 0; i < N; i++) t[i] = Set(i);

    MAGIC = -1;
    blockCount = 0;

    for (int i = 0; i < M; i++){
        unite(U[i], V[i]);

        if ((i + 1) % blockLength == 0 || i == M - 1){
            int id = blockCount++;

            el[id] = 0, er[id] = i;
            if (id > 0) el[id] = er[id - 1] + 1;

            for (int j = 0; j < N; j++) mem[j][id] = t[leader(j)];
        }

    }

    for (int i = 0; i < N; i++) flag[i] = false;
}

bool can(int x, int y){
    x = leader(x);
    y = leader(y);
    return x == y && !t[x].line;
}

int getMinimumFuelCapacity(int X, int Y) {
    int id = 0;
    while (id < blockCount){
        int xx = mem[X][id].parent, yy = mem[Y][id].parent;
        if (xx == yy && !mem[xx][id].line){
            break;
        } else {
            id++;
        }
    }

    if (id == blockCount) return -1;

    MAGIC = id;

    int ans = -1;

    re.clear();

    for (int i = el[id]; i <= er[id]; i++){
        auto [w, u, v] = edges[i];
        unite(u, v);
        if (can(X, Y)){
            ans = w;
            break;
        }
    }

    for (int i : re) flag[i] = false;

    return ans;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 203728 KB Output is correct
2 Correct 77 ms 203752 KB Output is correct
3 Correct 84 ms 203812 KB Output is correct
4 Correct 76 ms 203800 KB Output is correct
5 Correct 79 ms 203852 KB Output is correct
6 Correct 79 ms 203820 KB Output is correct
7 Correct 79 ms 203748 KB Output is correct
8 Correct 79 ms 203804 KB Output is correct
9 Correct 252 ms 207268 KB Output is correct
10 Correct 351 ms 207752 KB Output is correct
11 Correct 349 ms 207748 KB Output is correct
12 Correct 374 ms 207844 KB Output is correct
13 Correct 381 ms 207824 KB Output is correct
14 Correct 278 ms 207480 KB Output is correct
15 Correct 509 ms 209428 KB Output is correct
16 Correct 479 ms 209156 KB Output is correct
17 Correct 497 ms 209468 KB Output is correct
18 Correct 510 ms 209472 KB Output is correct
19 Execution timed out 2093 ms 206420 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 203728 KB Output is correct
2 Correct 77 ms 203752 KB Output is correct
3 Execution timed out 2088 ms 209192 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 203728 KB Output is correct
2 Correct 77 ms 203752 KB Output is correct
3 Correct 84 ms 203812 KB Output is correct
4 Correct 76 ms 203800 KB Output is correct
5 Correct 79 ms 203852 KB Output is correct
6 Correct 79 ms 203820 KB Output is correct
7 Correct 79 ms 203748 KB Output is correct
8 Correct 79 ms 203804 KB Output is correct
9 Correct 77 ms 203820 KB Output is correct
10 Incorrect 77 ms 203824 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 203820 KB Output is correct
2 Correct 80 ms 203728 KB Output is correct
3 Correct 77 ms 203752 KB Output is correct
4 Correct 84 ms 203812 KB Output is correct
5 Correct 76 ms 203800 KB Output is correct
6 Correct 79 ms 203852 KB Output is correct
7 Correct 79 ms 203820 KB Output is correct
8 Correct 79 ms 203748 KB Output is correct
9 Correct 79 ms 203804 KB Output is correct
10 Correct 252 ms 207268 KB Output is correct
11 Correct 351 ms 207752 KB Output is correct
12 Correct 349 ms 207748 KB Output is correct
13 Correct 374 ms 207844 KB Output is correct
14 Correct 381 ms 207824 KB Output is correct
15 Incorrect 77 ms 203824 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 203728 KB Output is correct
2 Correct 77 ms 203752 KB Output is correct
3 Correct 84 ms 203812 KB Output is correct
4 Correct 76 ms 203800 KB Output is correct
5 Correct 79 ms 203852 KB Output is correct
6 Correct 79 ms 203820 KB Output is correct
7 Correct 79 ms 203748 KB Output is correct
8 Correct 79 ms 203804 KB Output is correct
9 Correct 252 ms 207268 KB Output is correct
10 Correct 351 ms 207752 KB Output is correct
11 Correct 349 ms 207748 KB Output is correct
12 Correct 374 ms 207844 KB Output is correct
13 Correct 381 ms 207824 KB Output is correct
14 Correct 278 ms 207480 KB Output is correct
15 Correct 509 ms 209428 KB Output is correct
16 Correct 479 ms 209156 KB Output is correct
17 Correct 497 ms 209468 KB Output is correct
18 Correct 510 ms 209472 KB Output is correct
19 Execution timed out 2088 ms 209192 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 203820 KB Output is correct
2 Correct 80 ms 203728 KB Output is correct
3 Correct 77 ms 203752 KB Output is correct
4 Correct 84 ms 203812 KB Output is correct
5 Correct 76 ms 203800 KB Output is correct
6 Correct 79 ms 203852 KB Output is correct
7 Correct 79 ms 203820 KB Output is correct
8 Correct 79 ms 203748 KB Output is correct
9 Correct 79 ms 203804 KB Output is correct
10 Correct 252 ms 207268 KB Output is correct
11 Correct 351 ms 207752 KB Output is correct
12 Correct 349 ms 207748 KB Output is correct
13 Correct 374 ms 207844 KB Output is correct
14 Correct 381 ms 207824 KB Output is correct
15 Correct 278 ms 207480 KB Output is correct
16 Correct 509 ms 209428 KB Output is correct
17 Correct 479 ms 209156 KB Output is correct
18 Correct 497 ms 209468 KB Output is correct
19 Correct 510 ms 209472 KB Output is correct
20 Execution timed out 2088 ms 209192 KB Time limit exceeded
21 Halted 0 ms 0 KB -