제출 #887532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887532		TahirAliyev	게임 (IOI14_game)	C++17	42 / 100	1060 ms	6640 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;

set<pii> edges;

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;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            edges.insert({i, j});
        }
    }
}

int hasEdge(int u, int v) {
    if(u > v) swap(u, v);
    edges.erase({u, v});

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

    for(auto a : edges){
        unite(a.first, a.second, 1);
    }
    if(c != 1){
        rollback();
        unite(u, v, 0);
        return 1;
    }
    rollback();

    return 0;
}

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