Submission #558088

#	Time	Username	Problem	Language	Result	Execution time	Memory
558088		ljuba	Game (IOI14_game)	C++17	0 / 100	1 ms	308 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 2000;
int dsu[mxN];
int vel[mxN];

int findSet(int u) {
    if(dsu[u] == u) return u;
    return dsu[u] = findSet(dsu[u]);
}

bool unite(int u, int v) {
    u = findSet(u);
    v = findSet(v);

    if(u == v) return false;

    if(vel[u] > vel[v]) swap(u, v); //vel[u] <= vel[v]
    vel[v] += vel[u];
    dsu[u] = v;

    return true;
}

int komp;

void initialize(int N) {
    for(int i = 0; i < N; ++i) {
        dsu[i] = i;
        vel[i] = 1;
    }

    komp = N;
}

int hasEdge(int u, int v) {
    if(komp != 2) {
        u = findSet(u);
        v = findSet(v);
        if(u == v) {
            return 0;
        } else {
            --komp;
            unite(u, v);
            return 1;
        }
    }

    return 0;
}

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