Submission #887530

#	Time	Username	Problem	Language	Result	Execution time	Memory
887530		TahirAliyev	Game (IOI14_game)	C++17	0 / 100	1 ms	348 KiB

game

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

using namespace std;

#define pii pair<int, int>

const int MAX = 1505;

int N;
int par[MAX];

int c;
int get(int node){
    if(par[node] < 0) return node;
    return get(par[node]);
}

stack<array<int, 4>> calls;

void unite(int u, int v, bool isTemp){
    u = get(u);
    v = get(v);
    if(u == v) return;
    if(-par[u] < -par[v]) swap(u, v);
    if(isTemp){
        calls.push({u, v, par[u], par[v]});
    }
    par[u] += par[v];
    par[v] = u;
    c--;
}

void rollback(){
    while(calls.size()){
        auto a = calls.top();
        par[a[0]] = a[2];
        par[a[1]] = a[3];
        c++;
        calls.pop();
    }
}

void initialize(int n) {
    memset(par, -1, sizeof(par));
    N = n;
    c = n;
}

int hasEdge(int u, int v) {
    if(u > v) swap(u, v);

    unite(u, v, 1);
    if(c == 1){
        rollback();
        return 0;
    }
    rollback();
    unite(u, v, 0);
    return 1;
}

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