Submission #93533

#	Time	Username	Problem	Language	Result	Execution time	Memory
93533		Bodo171	Game (IOI14_game)	C++14	100 / 100	623 ms	34868 KiB

game

#include "game.h"
#include <iostream>
using namespace std;
const int nmax=1505;
int ad[nmax][nmax],grad[nmax][nmax];
bool asked[nmax][nmax];
int tt[nmax],rg[nmax];
int n,i;
void initialize(int N) {
    n=N;
    for(i=0;i<n;i++)
        tt[i]=i,rg[i]=1;
}
int finds(int x)
{
    while(x!=tt[x])
        x=tt[x];
    return x;
}
void unite(int A,int B)
{
    if(rg[A]<rg[B]) swap(A,B);
    tt[B]=A;rg[A]+=rg[B];
    for(int i=0;i<n;i++)
    {
        grad[A][i]+=grad[B][i];
        grad[i][A]+=grad[i][B];
    }
}
int hasEdge(int u, int v) {
    if(asked[u][v]) return ad[u][v];
    asked[u][v]=asked[v][u]=1;
    grad[finds(u)][finds(v)]++;
    grad[finds(v)][finds(u)]++;
    if(grad[finds(u)][finds(v)]==rg[finds(u)]*rg[finds(v)])
    {
        unite(finds(u),finds(v));
        ad[u][v]=ad[v][u]=1;
    }
    return ad[u][v];
}

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