Submission #588470

#	Time	Username	Problem	Language	Result	Execution time	Memory
588470		Vanilla	Game (IOI14_game)	C++17	0 / 100	1 ms	332 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int maxn = 1e3 + 5e2 + 2;
int dad[maxn];
int queries[maxn];
int comp, rem;

int find_dad(int x) {
    return dad[x] = (x == dad[x] ? x: find_dad(dad[x]));
}

void merge (int x, int y) {
    x = find_dad(x), y = find_dad(y);
    dad[x] = y;
}

void initialize(int n) {
    rem = n * (n - 1) / 2;
    comp = n;
    for (int i = 0; i < n; i++){
        queries[i] = n-1;
        dad[i] = i;
    }
}

int hasEdge(int u, int v) {
    queries[u]--;
    queries[v]--;
    if (find_dad(u) == find_dad(v)) {
        return 1;
    }
    if (comp == rem - 1) {
        merge(u,v);
        return 1;
    }
    if (queries[u] && queries[v]) {
        return 0;
    }
    else {
        merge(u,v);
        return 1;
    }
    rem--;
    return 0;
}

// int main() {
//     int n;
//     cin >> n;
//     initialize(n);
//     for (int i = 0; i < n * (n - 1) / 2; i++){
//         int x,y;
//         cout << i + 1 << "/" << n * (n - 1) / 2 << ": ";
//         cin >> x >> y;
//         cout << hasEdge(x,y) << endl;
//     }
// }

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