Submission #998273

#	Time	Username	Problem	Language	Result	Execution time	Memory
998273		The_Samurai	Game (IOI14_game)	C++17	42 / 100	1068 ms	860 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> p, size;
    void init(int n) {
        p.resize(n);
        size.assign(n, 1);
        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int get(int a) {
        return p[a] = p[a] == a ? a : get(p[a]);
    }

    void add(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

int n;
vector connected(1500, vector(1500, true));
dsu ds;

void initialize(int _n) {
    n = _n;
}

int hasEdge(int u, int v) {
    ds.init(n);
    connected[u][v] = connected[v][u] = false;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (connected[i][j]) ds.add(i, j);
        }
    }
    bool ok = true;
    for (int i = 1; i < n; i++) ok &= ds.get(0) == ds.get(i);
    if (!ok) connected[u][v] = connected[v][u] = true;
    return !ok;
}

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