oj.uz

Submission #369113

# Submission time Handle Problem Language Result Execution time Memory
369113 2021-02-20T11:26:42 Z mjhmjh1104 Game (IOI14_game) C++14
0 / 100
 1 ms 364 KB 
#include "game.h"

int uf[1506], sz[1506], ds[1506], n;

int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}

void _merge(int x, int y) {
    x = _find(x), y = _find(y);
    if (x == y) return;
    sz[y] += sz[x], uf[x] = y;
}

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; i++) uf[i] = -1, sz[i] = 1;
}

int hasEdge(int u, int v) {
    u = _find(u), v = _find(v);
    if (ds[u] + 1 == sz[u] * (n - sz[u]) || ds[v] + 1 == sz[v] * (n - sz[v])) {
        _merge(u, v);
        return 1;
    }
    ds[u]++, ds[v]++;
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 0 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -