Submission #648042

#	Time	Username	Problem	Language	Result	Execution time	Memory
648042		PoonYaPat	Game (IOI14_game)	C++14	15 / 100	1 ms	340 KiB

game

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

int n,p[1501],r[1501],com,cnt[1501],s;

int find(int x) {
    while (x!=p[x]) x=p[x];
    return x;
}

void unite(int x, int y) {
    x=find(x); y=find(y);
    if (r[x]<r[y]) swap(x,y);
    p[y]=x;
    if (r[x]==r[y])++r[x];
    --com;
}

void initialize(int N) {
    n=N; com=N;
    for (int i=1; i<=n; ++i) p[i]=i;
}

int hasEdge(int u, int v) {
    ++s;
    if (cnt[u]<n-2 && cnt[v]<n-2 && com<=n*(n-1)/2+1-s) {
        ++cnt[u];
        ++cnt[v];
        return 0;
    } else {
        unite(u,v);
        return 1;
    }
}

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