Submission #430600

#	Time	Username	Problem	Language	Result	Execution time	Memory
430600		muhammad_hokimiyon	Game (IOI14_game)	C++14	42 / 100	1086 ms	6420 KiB

game

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

using namespace std;

int N;
int p[2000];
int ss[2000];
set<pair<int, int>> s;
vector<pair<int, int>> g;

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

int get(int x)
{
        return (p[x] == x ? x : p[x] = get(p[x]));
}

void meg(int x, int y)
{
        x = get(x);
        y = get(y);
        if(x != y){
                p[y] = x;
                ss[x] += ss[y];
        }
}

int hasEdge(int u, int v)
{
        for(int i = 0; i < N; i++){
                p[i] = i;
                ss[i] = 1;
        }
        for(auto x : g){
                meg(x.first, x.second);
        }
        if(u > v)swap(u, v);
        s.erase({u, v});
        for(auto x : s){
                meg(x.first, x.second);
        }
        if(ss[get(1)] == N){
                return 0;
        }
        g.push_back({u, v});
        return 1;
}

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