Submission #997635

#	Time	Username	Problem	Language	Result	Execution time	Memory
997635		daffuwu	Game (IOI14_game)	C++14	100 / 100	228 ms	26708 KiB

game

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

int n, rep[1569], cnt[1569][1569];

int fd(int x)
{
    if (rep[x] != x) rep[x] = fd(rep[x]);
    return rep[x];
}

void initialize(int n) 
{
    ::n = n;
    int i, j;
    for (i=0; i<=n-1; i++)
    {
        rep[i] = i;
        for (j=i+1; j<=n-1; j++) cnt[i][j] = 1;
    }
}

int hasEdge(int u, int v) {
    int i;
    if (fd(u)>fd(v)) swap(u, v);
    if (cnt[fd(u)][fd(v)] == 1)
    {
        // u gabung ke v aja
        for (i=0; i<=n-1; i++) cnt[min(fd(v), i)][max(fd(v), i)] += cnt[min(fd(u), i)][max(fd(u), i)];
        rep[fd(u)] = fd(v);
        return 1; 
    }
    cnt[fd(u)][fd(v)]--;
    return 0;
}

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