oj.uz

답안 #714950

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

using namespace std;

const int MaxN = 100005;
const int MaxM = 200005;

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][MaxM / blockLength + 4];

vector<int> re; /// Todo: change to static array

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;
    }

    if (rand() & 1){
        swap(x, y);
        swap(X, Y);
    }

    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[MaxM], er[MaxM];

int blockCount;

vector<tuple<int, int, int>> edges;
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;

    assert(ans != -1);

    return ans;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 399568 KB Output is correct
2 Correct 153 ms 399464 KB Output is correct
3 Correct 153 ms 399468 KB Output is correct
4 Correct 161 ms 399472 KB Output is correct
5 Correct 153 ms 399596 KB Output is correct
6 Correct 154 ms 399460 KB Output is correct
7 Correct 163 ms 399520 KB Output is correct
8 Correct 170 ms 399512 KB Output is correct
9 Correct 341 ms 403048 KB Output is correct
10 Correct 429 ms 403392 KB Output is correct
11 Correct 421 ms 403440 KB Output is correct
12 Correct 458 ms 403452 KB Output is correct
13 Correct 463 ms 403524 KB Output is correct
14 Correct 341 ms 403192 KB Output is correct
15 Correct 569 ms 404944 KB Output is correct
16 Correct 598 ms 404932 KB Output is correct
17 Correct 598 ms 405060 KB Output is correct
18 Correct 613 ms 405124 KB Output is correct
19 Runtime error 566 ms 524288 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 399568 KB Output is correct
2 Correct 153 ms 399464 KB Output is correct
3 Runtime error 913 ms 524288 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 399568 KB Output is correct
2 Correct 153 ms 399464 KB Output is correct
3 Correct 153 ms 399468 KB Output is correct
4 Correct 161 ms 399472 KB Output is correct
5 Correct 153 ms 399596 KB Output is correct
6 Correct 154 ms 399460 KB Output is correct
7 Correct 163 ms 399520 KB Output is correct
8 Correct 170 ms 399512 KB Output is correct
9 Correct 162 ms 399508 KB Output is correct
10 Runtime error 540 ms 524288 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 399508 KB Output is correct
2 Correct 155 ms 399568 KB Output is correct
3 Correct 153 ms 399464 KB Output is correct
4 Correct 153 ms 399468 KB Output is correct
5 Correct 161 ms 399472 KB Output is correct
6 Correct 153 ms 399596 KB Output is correct
7 Correct 154 ms 399460 KB Output is correct
8 Correct 163 ms 399520 KB Output is correct
9 Correct 170 ms 399512 KB Output is correct
10 Correct 341 ms 403048 KB Output is correct
11 Correct 429 ms 403392 KB Output is correct
12 Correct 421 ms 403440 KB Output is correct
13 Correct 458 ms 403452 KB Output is correct
14 Correct 463 ms 403524 KB Output is correct
15 Runtime error 540 ms 524288 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 399568 KB Output is correct
2 Correct 153 ms 399464 KB Output is correct
3 Correct 153 ms 399468 KB Output is correct
4 Correct 161 ms 399472 KB Output is correct
5 Correct 153 ms 399596 KB Output is correct
6 Correct 154 ms 399460 KB Output is correct
7 Correct 163 ms 399520 KB Output is correct
8 Correct 170 ms 399512 KB Output is correct
9 Correct 341 ms 403048 KB Output is correct
10 Correct 429 ms 403392 KB Output is correct
11 Correct 421 ms 403440 KB Output is correct
12 Correct 458 ms 403452 KB Output is correct
13 Correct 463 ms 403524 KB Output is correct
14 Correct 341 ms 403192 KB Output is correct
15 Correct 569 ms 404944 KB Output is correct
16 Correct 598 ms 404932 KB Output is correct
17 Correct 598 ms 405060 KB Output is correct
18 Correct 613 ms 405124 KB Output is correct
19 Runtime error 913 ms 524288 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 399508 KB Output is correct
2 Correct 155 ms 399568 KB Output is correct
3 Correct 153 ms 399464 KB Output is correct
4 Correct 153 ms 399468 KB Output is correct
5 Correct 161 ms 399472 KB Output is correct
6 Correct 153 ms 399596 KB Output is correct
7 Correct 154 ms 399460 KB Output is correct
8 Correct 163 ms 399520 KB Output is correct
9 Correct 170 ms 399512 KB Output is correct
10 Correct 341 ms 403048 KB Output is correct
11 Correct 429 ms 403392 KB Output is correct
12 Correct 421 ms 403440 KB Output is correct
13 Correct 458 ms 403452 KB Output is correct
14 Correct 463 ms 403524 KB Output is correct
15 Correct 341 ms 403192 KB Output is correct
16 Correct 569 ms 404944 KB Output is correct
17 Correct 598 ms 404932 KB Output is correct
18 Correct 598 ms 405060 KB Output is correct
19 Correct 613 ms 405124 KB Output is correct
20 Runtime error 913 ms 524288 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -