Submission #648051

#	Time	Username	Problem	Language	Result	Execution time	Memory
648051		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,sz[1501];

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;
    sz[x]+=sz[y];
    cnt[x]+=cnt[y];
    if (r[x]==r[y])++r[x];
    --com;
}

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

int hasEdge(int u, int v) {
    ++s;
    u=find(u); v=find(v);
    if (u==v) return 1;

    if (cnt[u]<(n-sz[u])*sz[u]-1 && cnt[v]<(n-sz[v])*sz[v]-1 && 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