Submission #1013090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013090		Luvidi	Game (IOI14_game)	C++17	100 / 100	224 ms	26448 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int n,par[1500],sz[1500],cnt[1500][1500];

int rep(int x){
    while(x!=par[x])x=par[x];
    return x;
}

void join(int x,int y){
    if(sz[x]>sz[y])swap(x,y);
    par[x]=y;
    sz[y]+=sz[x];
    for(int i=0;i<n;i++){
        if(par[i]!=i)continue;
        if(i==y)continue;
        cnt[y][i]+=cnt[x][i];
        cnt[i][y]+=cnt[i][x];
    }
}

void initialize(int x) {
    n=x;
    for(int i=0;i<n;i++){
        par[i]=i;
        sz[i]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cnt[i][j]=1;
    }
}

int hasEdge(int u, int v) {
    u=rep(u);
    v=rep(v);
    cnt[u][v]--;
    cnt[v][u]--;
    if(u==v)return 1;
    if(cnt[u][v])return 0;
    join(u,v);
    return 1;
}

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