oj.uz

답안 #714954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714954 2023-03-25T14:59:40 Z dxz05 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 361276 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

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

int N, M;
const int blockLength = 900;

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

int re[MaxN];
int _nxt;

int leader(int x){
    if (MAGIC != -1 && !flag[x]){
        t[x] = (MAGIC == 0 ? Set(x) : mem[x][MAGIC - 1]);
        flag[x] = true;
        re[_nxt++] = 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;

    _nxt = 0;

    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 = 0; i < _nxt; i++) flag[re[i]] = false;

    return ans;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 355720 KB Output is correct
2 Correct 169 ms 355600 KB Output is correct
3 Correct 165 ms 355604 KB Output is correct
4 Correct 171 ms 355656 KB Output is correct
5 Correct 165 ms 355656 KB Output is correct
6 Correct 165 ms 355632 KB Output is correct
7 Correct 163 ms 355660 KB Output is correct
8 Correct 165 ms 355720 KB Output is correct
9 Correct 335 ms 359136 KB Output is correct
10 Correct 424 ms 359544 KB Output is correct
11 Correct 477 ms 359608 KB Output is correct
12 Correct 466 ms 359716 KB Output is correct
13 Correct 469 ms 359620 KB Output is correct
14 Correct 352 ms 359324 KB Output is correct
15 Correct 603 ms 361120 KB Output is correct
16 Correct 563 ms 361096 KB Output is correct
17 Correct 577 ms 361200 KB Output is correct
18 Correct 579 ms 361276 KB Output is correct
19 Execution timed out 2090 ms 358196 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 355720 KB Output is correct
2 Correct 169 ms 355600 KB Output is correct
3 Execution timed out 2079 ms 360992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 355720 KB Output is correct
2 Correct 169 ms 355600 KB Output is correct
3 Correct 165 ms 355604 KB Output is correct
4 Correct 171 ms 355656 KB Output is correct
5 Correct 165 ms 355656 KB Output is correct
6 Correct 165 ms 355632 KB Output is correct
7 Correct 163 ms 355660 KB Output is correct
8 Correct 165 ms 355720 KB Output is correct
9 Correct 171 ms 355664 KB Output is correct
10 Incorrect 243 ms 355676 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 355664 KB Output is correct
2 Correct 164 ms 355720 KB Output is correct
3 Correct 169 ms 355600 KB Output is correct
4 Correct 165 ms 355604 KB Output is correct
5 Correct 171 ms 355656 KB Output is correct
6 Correct 165 ms 355656 KB Output is correct
7 Correct 165 ms 355632 KB Output is correct
8 Correct 163 ms 355660 KB Output is correct
9 Correct 165 ms 355720 KB Output is correct
10 Correct 335 ms 359136 KB Output is correct
11 Correct 424 ms 359544 KB Output is correct
12 Correct 477 ms 359608 KB Output is correct
13 Correct 466 ms 359716 KB Output is correct
14 Correct 469 ms 359620 KB Output is correct
15 Incorrect 243 ms 355676 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 355720 KB Output is correct
2 Correct 169 ms 355600 KB Output is correct
3 Correct 165 ms 355604 KB Output is correct
4 Correct 171 ms 355656 KB Output is correct
5 Correct 165 ms 355656 KB Output is correct
6 Correct 165 ms 355632 KB Output is correct
7 Correct 163 ms 355660 KB Output is correct
8 Correct 165 ms 355720 KB Output is correct
9 Correct 335 ms 359136 KB Output is correct
10 Correct 424 ms 359544 KB Output is correct
11 Correct 477 ms 359608 KB Output is correct
12 Correct 466 ms 359716 KB Output is correct
13 Correct 469 ms 359620 KB Output is correct
14 Correct 352 ms 359324 KB Output is correct
15 Correct 603 ms 361120 KB Output is correct
16 Correct 563 ms 361096 KB Output is correct
17 Correct 577 ms 361200 KB Output is correct
18 Correct 579 ms 361276 KB Output is correct
19 Execution timed out 2079 ms 360992 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 355664 KB Output is correct
2 Correct 164 ms 355720 KB Output is correct
3 Correct 169 ms 355600 KB Output is correct
4 Correct 165 ms 355604 KB Output is correct
5 Correct 171 ms 355656 KB Output is correct
6 Correct 165 ms 355656 KB Output is correct
7 Correct 165 ms 355632 KB Output is correct
8 Correct 163 ms 355660 KB Output is correct
9 Correct 165 ms 355720 KB Output is correct
10 Correct 335 ms 359136 KB Output is correct
11 Correct 424 ms 359544 KB Output is correct
12 Correct 477 ms 359608 KB Output is correct
13 Correct 466 ms 359716 KB Output is correct
14 Correct 469 ms 359620 KB Output is correct
15 Correct 352 ms 359324 KB Output is correct
16 Correct 603 ms 361120 KB Output is correct
17 Correct 563 ms 361096 KB Output is correct
18 Correct 577 ms 361200 KB Output is correct
19 Correct 579 ms 361276 KB Output is correct
20 Execution timed out 2079 ms 360992 KB Time limit exceeded
21 Halted 0 ms 0 KB -