Submission #201742

#	Time	Username	Problem	Language	Result	Execution time	Memory
201742		DavidDamian	Game (IOI14_game)	C++11	100 / 100	537 ms	25380 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
///Disjoint Sets
///Create a tree in exactly n(n-1)/2 movements
int n;
int link[1505];
int setSize[1505];
int root(int u)
{
    if(link[u]==u) return u;
    else return link[u]=root(link[u]);
}
void join(int a,int b)
{
    a=root(a);
    b=root(b);
    if(a==b) return;
    if(setSize[a]<setSize[b]) swap(a,b);
    link[b]=a;
    setSize[a]+=setSize[b];
}
int maybe[1505][1505]; //Maybe[i][j] is the number of edges between nodes i,j that are not asked yet
void initialize(int N) {
    n=N;
    for(int i=0;i<n;i++){
        link[i]=i;
        setSize[i]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            maybe[i][j]=1; //There is a possible edge from each note to other
        }
    }
}
int hasEdge(int u, int v) {
    u=root(u);
    v=root(v);
    if(maybe[u][v]==1){ //The last edge between those components, so we use it
        if(setSize[v]>setSize[u]) swap(u,v);
        for(int i=0;i<n;i++){
            maybe[i][u]+=maybe[i][v]; //We add the edges of component v to component u
            maybe[u][i]+=maybe[v][i];
        }
        join(u,v);
        return 1;
    }
    else{ //Too many edges, we discard it
        maybe[u][v]--;
        maybe[v][u]--;
        return 0;
    }
}

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