Submission #556460

#	Time	Username	Problem	Language	Result	Execution time	Memory
556460		n0sk1ll	Game (IOI14_game)	C++14	42 / 100	1095 ms	6404 KiB

game

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

using namespace std;

int n;
set<pair<int,int>> ed;

int up[1505];

int Up(int x)
{
    if (up[x]==x) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b);
    up[a]=b;
}

bool connected()
{
    for (int i=0;i<n;i++) up[i]=i;
    for (auto it : ed) dsu(it.first,it.second);

    int komp=0;
    for (int i=0;i<n;i++) if (up[i]==i) komp++;
    return komp==1;
}

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

int hasEdge(int u, int v) {
    if (u>v) swap(u,v);
    ed.erase({u,v});
    if (connected()) return 0;
    return ed.insert({u,v}),1;
}

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