Submission #1032419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032419		vjudge1	Game (IOI14_game)	C++17	42 / 100	1049 ms	5980 KiB

game

#include "game.h"

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

unordered_set<int>p[1500];

int N;

void initialize(int n){
    N=n;
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            p[i].insert(j);
        }
    }
}

struct{
    int par[1500];
    void init(int n){
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    int find(int i){
        if(par[i]==i)return i;
        return par[i]=find(par[i]);
    }
    void unite(int i,int j){
        i=find(i),j=find(j);
        par[i]=j;
    }
}dsu;

int hasEdge(int u, int v) {
    if(v<u)swap(u,v);
    p[v].erase(u);
    dsu.init(N);
    for(int i=1;i<N;i++){
        for(int j:p[i]){
            dsu.unite(i,j);
        }
    }
    for(int i=1;i<N;i++){
        if(dsu.find(0)!=dsu.find(i)){
            p[v].insert(u);
            return 1;
        }
    }
    return 0;
}

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