oj.uz

답안 #714960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714960 2023-03-25T15:24:18 Z dxz05 자매 도시 (APIO20_swap) C++17
6 / 100
 475 ms 365356 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")

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

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MaxN = 100002;
const int MaxM = 200002;

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

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 (rng() & 1){
        swap(x, y);
        swap(X, 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[MaxM], er[MaxM];

int blockCount;

tuple<int, int, int> edges[MaxM];
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[i] = make_tuple(W[i], U[i], V[i]);
    }

    sort(edges, edges + M);

    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) {
    if (M == N - 1) return -1;
    if (M == N) return get<0>(edges[M - 1]);

    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;

    assert(ans != -1);

    return ans;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 354080 KB Output is correct
2 Correct 166 ms 354128 KB Output is correct
3 Correct 157 ms 354212 KB Output is correct
4 Correct 161 ms 354172 KB Output is correct
5 Correct 174 ms 354092 KB Output is correct
6 Correct 168 ms 354096 KB Output is correct
7 Correct 164 ms 354268 KB Output is correct
8 Correct 169 ms 354144 KB Output is correct
9 Correct 320 ms 356952 KB Output is correct
10 Correct 369 ms 357564 KB Output is correct
11 Correct 371 ms 357488 KB Output is correct
12 Correct 420 ms 357744 KB Output is correct
13 Correct 426 ms 357664 KB Output is correct
14 Correct 298 ms 357052 KB Output is correct
15 Correct 431 ms 359444 KB Output is correct
16 Correct 430 ms 359320 KB Output is correct
17 Correct 452 ms 359496 KB Output is correct
18 Correct 449 ms 359544 KB Output is correct
19 Correct 219 ms 358016 KB Output is correct
20 Correct 454 ms 364700 KB Output is correct
21 Correct 406 ms 364988 KB Output is correct
22 Correct 475 ms 365296 KB Output is correct
23 Correct 462 ms 365356 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 354080 KB Output is correct
2 Correct 166 ms 354128 KB Output is correct
3 Incorrect 411 ms 359360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 354080 KB Output is correct
2 Correct 166 ms 354128 KB Output is correct
3 Correct 157 ms 354212 KB Output is correct
4 Correct 161 ms 354172 KB Output is correct
5 Correct 174 ms 354092 KB Output is correct
6 Correct 168 ms 354096 KB Output is correct
7 Correct 164 ms 354268 KB Output is correct
8 Correct 169 ms 354144 KB Output is correct
9 Correct 185 ms 354252 KB Output is correct
10 Incorrect 157 ms 354152 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 354252 KB Output is correct
2 Correct 164 ms 354080 KB Output is correct
3 Correct 166 ms 354128 KB Output is correct
4 Correct 157 ms 354212 KB Output is correct
5 Correct 161 ms 354172 KB Output is correct
6 Correct 174 ms 354092 KB Output is correct
7 Correct 168 ms 354096 KB Output is correct
8 Correct 164 ms 354268 KB Output is correct
9 Correct 169 ms 354144 KB Output is correct
10 Correct 320 ms 356952 KB Output is correct
11 Correct 369 ms 357564 KB Output is correct
12 Correct 371 ms 357488 KB Output is correct
13 Correct 420 ms 357744 KB Output is correct
14 Correct 426 ms 357664 KB Output is correct
15 Incorrect 157 ms 354152 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 354080 KB Output is correct
2 Correct 166 ms 354128 KB Output is correct
3 Correct 157 ms 354212 KB Output is correct
4 Correct 161 ms 354172 KB Output is correct
5 Correct 174 ms 354092 KB Output is correct
6 Correct 168 ms 354096 KB Output is correct
7 Correct 164 ms 354268 KB Output is correct
8 Correct 169 ms 354144 KB Output is correct
9 Correct 320 ms 356952 KB Output is correct
10 Correct 369 ms 357564 KB Output is correct
11 Correct 371 ms 357488 KB Output is correct
12 Correct 420 ms 357744 KB Output is correct
13 Correct 426 ms 357664 KB Output is correct
14 Correct 298 ms 357052 KB Output is correct
15 Correct 431 ms 359444 KB Output is correct
16 Correct 430 ms 359320 KB Output is correct
17 Correct 452 ms 359496 KB Output is correct
18 Correct 449 ms 359544 KB Output is correct
19 Incorrect 411 ms 359360 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 354252 KB Output is correct
2 Correct 164 ms 354080 KB Output is correct
3 Correct 166 ms 354128 KB Output is correct
4 Correct 157 ms 354212 KB Output is correct
5 Correct 161 ms 354172 KB Output is correct
6 Correct 174 ms 354092 KB Output is correct
7 Correct 168 ms 354096 KB Output is correct
8 Correct 164 ms 354268 KB Output is correct
9 Correct 169 ms 354144 KB Output is correct
10 Correct 320 ms 356952 KB Output is correct
11 Correct 369 ms 357564 KB Output is correct
12 Correct 371 ms 357488 KB Output is correct
13 Correct 420 ms 357744 KB Output is correct
14 Correct 426 ms 357664 KB Output is correct
15 Correct 298 ms 357052 KB Output is correct
16 Correct 431 ms 359444 KB Output is correct
17 Correct 430 ms 359320 KB Output is correct
18 Correct 452 ms 359496 KB Output is correct
19 Correct 449 ms 359544 KB Output is correct
20 Incorrect 411 ms 359360 KB Output isn't correct
21 Halted 0 ms 0 KB -