Submission #234939

#	Time	Username	Problem	Language	Result	Execution time	Memory
234939		anonymous	Game (IOI14_game)	C++14	0 / 100	5 ms	384 KiB

game

#include "game.h"
#include <iostream>
#define MAXN 1505
using namespace std;
int Ops[MAXN], N;
class DSU {
public:
    int Set[MAXN][2];
    void init(int n) {
        for (int i=0; i<=n; i++) {Set[i][0] = i, Set[i][1] = 1;}
    }
    int Find(int x) {
        return(Set[x][0] == x ? x : Set[x][0] = Find(Set[x][0]));
    }
    int Sz(int x) {return(Set[Find(x)][1]);}
    void Union(int x, int y) {
        int p1 = Find(x), p2 = Find(y);
        if (Set[p1][1] > Set[p2][1]) {swap(p1,p2);}
        Set[p2][1] += Set[p1][1], Set[p1][0] = p2;
    }
} UF;

void initialize(int n) {
    UF.init(n), N=n;
}

int hasEdge(int u, int v) {
    int v1 = UF.Sz(u) + Ops[u], v2 = UF.Sz(v) + Ops[v];
    if (max(v1,v2) == N-1) {
        UF.Union(u,v);
        return(true);
    } else {
        Ops[u]++, Ops[v]++;
        return(false);
    }
}

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