oj.uz

Submission #934468

# Submission time Handle Problem Language Result Execution time Memory
934468 2024-02-27T11:29:32 Z peterandvoi Game (IOI14_game) C++17
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1500;

int _n, cc;
int e[N];
int cnt[N][N];
int cant[N];

int get(int u) {
    return e[u] < 0 ? u : e[u] = get(e[u]);
}

void join(int u, int v) {
    if (e[u] > e[v]) {
        swap(u, v);
    }
    e[u] += e[v];
    e[v] = u;
    cant[u] = 0;
    for (int i = 0; i < _n; ++i) {
        if (i != u && get(i) == i) {
            cnt[u][i] += cnt[v][i];
        } else {
            cnt[u][i] = 0;
        }
        cant[u] += cnt[u][i] == 0;
    }
    for (int i = 0; i < _n; ++i) {
        if (i != u && get(i) == i) {
            cant[i] -= cnt[i][v] == 0;
            cant[i] -= cnt[i][u] == 0;
            cnt[i][u] += cnt[i][v];
            cnt[i][v] = 0;
            cant[i]++;
            cant[i] += cnt[i][u] == 0;
        }
    }
}

bool same(int u, int v) {
    return get(u) == get(v);
}

bool need_merge(int u) {
    return cant[u] == _n - 1;
}

void initialize(int n) {
    _n = n;
    cc = _n;
    fill(e, e + n, -1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                cnt[i][j]++;
            }
        }
        cant[i] = 1;
    }
}

int hasEdge(int u, int v) {
    if (same(u, v)) {
        return 0;
    }
    u = get(u);
    v = get(v);
    if (cnt[u][v] == 1 && (need_merge(u) || need_merge(v))) {
        join(u, v);
        cc--;
        return 1;
    }
    cnt[u][v]--;
    cnt[v][u]--;
    cant[u] += cnt[u][v] == 0;
    cant[v] += cnt[u][v] == 0;
    return 0;
}

#ifdef ngu
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int n;
    cin >> n;
    initialize(n);
    for (int i = 0; i < n; ++i) {
        debug(i, get(i));
    }
    for (int i = 0; i < n * (n - 1) / 2; ++i) {
        int u, v;
        cin >> u >> v;
        assert(cc > 1);
        debug(u, v, hasEdge(u, v));
        for (int j = 0; j < n; ++j) {
            debug(j, cant[j]);
        }
    }
    assert(cc == 1);
}
#endif

Subtask #1
0 / 15.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 58.0

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