Submission #309175

#	Time	Username	Problem	Language	Result	Execution time	Memory
309175		mohamedsobhi777	Game (IOI14_game)	C++14	100 / 100	592 ms	25976 KiB

game

#include<bits/stdc++.h>
#include "game.h"

const int MX = 1600 + 7 ; 
using namespace std ; 

int fat[MX] ; 
int gn ; 
int del[MX][MX] ;
int g[MX][MX] ;  
int sz[MX] ; 

int now , prv ;

inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; }  

void link(int u , int v){
        u = find(u) ; 
        v = find(v) ; 
        if(u != v){
                sz[v] += sz[u] ; 
                sz[u] = 0 ; 
                fat[u] = v ;
                now = v ; 
                prv = u ; 
        }
}

void initialize(int x){
        gn = x ; 
        for(int i = 0 ; i < x ; ++ i)
                fat[i] = i , sz[i] = 1; 
}

int hasEdge(int u, int v) {
        if(u > v)swap(u , v) ; 
        int a = find(u) ;       
        int b = find(v) ; 
        if(a == b){
                return 1 ; 
        }

        if(sz[a] * sz[b] != g[a][b] + 1){
                g[a][b] ++ ; 
                g[b][a] ++ ; 
                return 0; 
        }

        link(u , v) ;
        for(int i = 0 ;i < gn ; ++ i){
                g[i][now] += g[i][prv] ; 
                g[now][i] = g[i][now] ; 
                g[i][prv] = g[prv][i] = 0 ; 
        }

        return 1 ; 
}

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