[IOI 2014] Game

https://www.acmicpc.net/problem/10071

 

말리면 한없이 말린다.

 

42점은 간단하게, '더 이상 연결성이 보장되지 않는 시점에 잇는다'를 구현했고, 이걸 확장해서 100점을 만들려니 환장하겠더라.

residual 그래프에 $K_{i,n-i}$꼴이 발생하면 연결한다 이딴걸 해볼까? 온라인으로 단절선을 관리할 수가 있나? 이게 플래 1인가?

 

엄청 말렸는데, 그냥 괜찮은 construction을 만드는게 문제의 방향이었다.

떠올린 다음에.. 지나간 한 두 시간을 되새기며 '이게 맞나? 정말?'이라는 말을 하며 제출했는데 맞았다.

 

제너레이터를 이용해 랜덤한 트리를 만들어 본 경험을 떠올리면서 발상했던 것 같다.

기이한 문제..

 

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

int deg[1503];
int n;

void initialize(int _n) {
    n = _n;
    for(int i=0;i<n;++i) deg[i]=i;
}

int hasEdge(int u, int v) {
    if(u>v)swap(u,v);
    
    if(--deg[v]) {
        return 0;
    }
    else {
        return 1;
    }
}