Submission #227001

#	Time	Username	Problem	Language	Result	Execution time	Memory
227001		Charis02	Game (IOI14_game)	C++14	100 / 100	566 ms	15992 KiB

game

#include "game.h"
#define N 1505

int par[N],edges[N][N],sz[N],nn;

int f(int x)
{
    if(par[x]==x)
        return x;

    return par[x]=f(par[x]);
}

bool issameset(int x,int y)
{
    int fx=f(x);
    int fy = f(y);

    return (fx==fy);
}

void join(int x,int y)
{
    int fx = f(x);
    int fy = f(y);

    if(sz[fx] > sz[fy])
    {
        fx^=fy;
        fy^=fx;
        fx^=fy;
    }

    par[fx] = fy;
    sz[fy]+=sz[fx];

    for(int i = 0;i < nn;i++)
    {
        edges[fy][i] += edges[fx][i];
        edges[fx][i] = 0;
    }

    for(int i = 0;i < nn;i++)
    {
        edges[i][fy] += edges[i][fx];
        edges[i][fx] = 0;
    }

    return;
}

void initialize(int n)
{
    nn = n;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(i==j)
                continue;

            edges[i][j]=1;
        }

        sz[i]=1;
        par[i]=i;
    }

    return;
}

int hasEdge(int u, int v)
{
    if(issameset(u,v))
        return 0;

    int fu = f(u);
    int fv = f(v);

    edges[fu][fv]--;
    edges[fv][fu]--;

    if(edges[fu][fv] == 0)
    {
        join(fu,fv);
        return 1;
    }
    else
        return 0;
}

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