Submission #634296

#	Time	Username	Problem	Language	Result	Execution time	Memory
634296		ljuba	Game (IOI14_game)	C++17	0 / 100	1 ms	212 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