Submission #83330

#	Time	Username	Problem	Language	Result	Execution time	Memory
83330		gs18115	Game (IOI14_game)	C++14	100 / 100	628 ms	160516 KiB

game

#include"game.h"
int V;
int pa[1505];
int eg[1505][1505];
void initialize(int n)
{
    V=n;
    for(int i=0;i<n;i++)
    {
        pa[i]=-1;
        for(int j=i+1;j<n;j++)
            eg[i][j]=eg[j][i]=1;
    }
    return;
}
int par(const int&x)
{
    if(pa[x]==-1)
        return x;
    return pa[x]=par(pa[x]);
}
inline void uni(const int&x,const int&y)
{
    pa[y]=x;
    for(int i=0;i<V;i++)
    {
        if(i==x||i==y)
            continue;
        eg[x][i]+=eg[y][i];
        eg[i][x]+=eg[i][y];
        eg[y][i]=eg[i][y]=0;
    }
    return;
}
int hasEdge(int u,int v)
{
    u=par(u);
    v=par(v);
    if(u==v)
        return 0;
    eg[u][v]--;
    eg[v][u]--;
    if(eg[u][v]==0)
    {
        uni(u,v);
        return 1;
    }
    return 0;
}

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