Submission #936020

#	Time	Username	Problem	Language	Result	Execution time	Memory
936020		peterandvoi	Game (IOI14_game)	C++17	100 / 100	266 ms	27260 KiB

game

#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int>> cnt;
vector<int> lab;

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

int hasEdge(int u, int v) {
    u = get(u);
    v = get(v);
    assert(u != v);
    if (cnt[u][v] > 1) {
        cnt[u][v]--;
        cnt[v][u]--;
        return 0;
    }
    if (lab[u] > lab[v]) {
        swap(u, v);
    }
    lab[u] += lab[v];
    lab[v] = u;
    for (int i = 0; i < (int) lab.size(); ++i) {
        cnt[u][i] += cnt[v][i];
        cnt[i][u] = cnt[u][i];
    }
    return 1;
}

void initialize(int n) {
    cnt.resize(n, vector<int>(n));
    lab.resize(n, -1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cnt[i][j] = i != j;
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58