Submission #412815

#	Time	Username	Problem	Language	Result	Execution time	Memory
412815		pliam	Game (IOI14_game)	C++14	100 / 100	494 ms	25260 KiB

game

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

int parent[MAXN],height[MAXN];
int rem[MAXN][MAXN];
int N;

int find_set(int v){
    if(parent[v]==v) return v;
    else return parent[v]=find_set(parent[v]);
}

bool is_connected(int a,int b){
    return find_set(a)==find_set(b);
}

void union_sets(int a,int b){
    a=find_set(a);
    b=find_set(b);
    if(a==b) return;
    if(height[a]<height[b]) swap(a,b);
    parent[b]=a;
    if(height[a]==height[b]) height[a]++;
    for(int i=0;i<N;i++){
        rem[a][i]+=rem[b][i];
        rem[i][a]+=rem[i][b];
    }
}

void initialize(int n) {
    N=n;
    for(int i=0;i<n;i++){
        parent[i]=i;
        height[i]=0;
        for(int j=0;j<n;j++){
            if(i==j) continue;
            rem[i][j]=1;
        }
    }
}

int hasEdge(int u, int v) {
    u=find_set(u);
    v=find_set(v);
    if(u==v){
        return 1;
    }else{
        if(rem[u][v]>1){
            rem[u][v]--;
            rem[v][u]--;
            return 0;
        }else{
            union_sets(u,v);
            return 1;
        }
    }
}

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