Submission #1016909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016909		vivkostov	Game (IOI14_game)	C++14	100 / 100	239 ms	21112 KiB

game

#include<bits/stdc++.h>
#define endl '\n'
#include "game.h"
using namespace std;
int br[2005][2005],n,lead[2005];
int fix_lead(int beg)
{
    if(lead[beg]==beg)return beg;
    return fix_lead(lead[beg]);
}
void merg(int v,int u)
{
    v=fix_lead(v);
    u=fix_lead(u);
    br[v][u]--;
    br[u][v]--;
    for(int i=1;i<=n;i++)
    {
        br[v][i]+=br[u][i];
        br[i][v]+=br[i][u];
        br[u][i]=0;
        br[i][u]=0;
    }
    lead[u]=v;
}
void initialize(int N)
{
    n=N;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            br[i][j]=1;
        }
        lead[i]=i;
    }
}
int hasEdge(int v,int u)
{
    v++;
    u++;
    v=fix_lead(v);
    u=fix_lead(u);
    if(br[v][u]==1)
    {
        merg(v,u);
        return 1;
    }
    else
    {
        br[v][u]--;
        br[u][v]--;
        return 0;
    }
}

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