Submission #730331

#	Time	Username	Problem	Language	Result	Execution time	Memory
730331		sofija6	Game (IOI14_game)	C++14	100 / 100	346 ms	25220 KiB

game

#include <bits/stdc++.h>
#define MAXN 1510
using namespace std;
int cnt[MAXN][MAXN],d[MAXN],N;
int Root(int p)
{
    while (d[p]!=p)
    {
        d[p]=d[d[p]];
        p=d[p];
    }
    return p;
}
void Join(int u,int v)
{
    int ru=Root(u),rv=Root(v);
    if (rv<ru)
        swap(ru,rv);
    d[rv]=ru;
    for (int i=0;i<N;i++)
    {
        cnt[ru][i]+=cnt[rv][i];
        cnt[i][ru]+=cnt[rv][i];
    }
}
void initialize(int n)
{
    N=n;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
            cnt[i][j]=1;
        d[i]=i;
    }
}
int hasEdge(int u, int v)
{
    int ru=Root(u),rv=Root(v);
    if (ru!=rv && cnt[ru][rv]==1)
    {
        Join(ru,rv);
        return 1;
    }
    cnt[ru][rv]--;
    cnt[rv][ru]--;
    return 0;
}

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