[백준] 14676 영우는 사기꾼?

문제

영선이와 영우는 최근 ‘우주전쟁’ 이라는 게임을 시작했다. ‘우주전쟁’은 1대1로 하는 RTS(실시간 전략 게임) 게임으로, 각 플레이어는 건물을 건설하고, 건물에서 유닛을 생성하여 싸운다. ‘우주전쟁’은 건물을 짓는 순서가 정해져 있는데, 예를 들어 건물들이 다음과 같은 관계도를 가진다고 할 때,

2, 3번 건물은 반드시 1번 건물이 건설된 상태여야 지어질 수 있고, 4번 건물은 반드시 2, 3번 건물이 건설된 상태여야 지어질 수 있다. 단 4번 건물은 1번 건물과는 직접적인 연관이 없기 때문에 1번 건물이 없다고 하더 라도 4번 건물은 건설이 가능하다. 이때 1번 건물은 2, 3번 건물에 영향을 미친다고 할 수 있고, 2, 3번 건물은 4번 건물에 영향을 미친다고 할 수 있다. 또한 모든 건물들은 중복 건설이 가능하다. ‘우주전쟁’ 게임의 제작사 인 ‘얼음폭풍’사는 게임의 밸런스를 유지하기 위해 한 건물은 최대 3개의 건물에게만 영향을 미치도록 하였다. 또 ‘우주전쟁’ 게임에는 치트키가 하나 있는데, 이 치트키를 사용하면 원하는 건물을 마음대로 설치할 수 있다. 하지만 이 치트키를 사용하면 너무나 쉽게 게임에서 이길 수 있기 때문에 영선이와 영우는 서로 치트키를 쓰 지 않기로 약속했다. 하지만 이상하게도 영우는 영선이와의 게임에서 모두 승리하였고, 그런 영우를 이상하게 여긴 영선이는 영우의 건물 건설/파괴 정보를 가져왔다. (치트키로 건설한 건물은 건설 정보에 들어가지 않는 다.) 영우의 게임정보를 보고 영우가 치트키를 사용했는지 판단하는 프로그램을 만들어 영선이를 도와주자.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 건물의 관계인 X Y 가 차례대로 중복 없이 주어진다. (X를 건설해야 Y를 건설할 수 있음.) (1 ≤ X, Y ≤ N) 다음 줄부터 K줄에 걸쳐 영우의 게임 정보가 다음과 같이 주어진다. (1 ≤ a ≤ N)

• 1 a(영우가 a번 건물을 1개 건설함)
• 2 a(영우의 a번 건물이 1개 파괴됨)

출력

프로그램의 출력은 표준 출력으로 한다. 영우가 정상적으로 건물을 건설하거나, 건설한 만큼의 건물만 파괴되 었다면 ‘King-God-Emperor’를. 건설할 수 없는 건물을 건설하거나, 건설한적 없는 건물이 파괴되었다면 ‘Lier!’ 를 출력하자.

 

 

위상정렬 문제입니다.

하지만 한종류의 건물을 여러개 지을 수 있습니다.

따라서 단순히 큐를이용해서 건물을 지을 수 있는지 없는지 확인할 수 없고,

매번 이 건물을 지을 수 있는지 없는지 현재 지어진 건물의 정보를 바탕으로 확인해야 합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int a, b, N, M, K, n[100001], bu[100001], canbuild[100001];
vi adj[100001], jda[100001];
bool build(int k) {
	if (!canbuild[k])return 0;
	bu[k]++;
	for (auto r : adj[k]) {
		int f = 1;
		for (auto c : jda[r]) {
			if (!bu[c]) {
				f = 0; break;
			}
		}
		if (f)canbuild[r] = 1;
	}
	return 1;
}
bool destroy(int k) {
	if (!bu[k])return 0;
	if (!(--bu[k])) {
		for (auto r : adj[k]) {
			canbuild[r] = 0;
		}
	}

	return 1;
}
int main() {
	FAST;
	cin >> N >> M >> K;
	while (M--) {
		cin >> a >> b;
		n[b]++;
		adj[a].push_back(b);
		jda[b].push_back(a);
	}
	REP(i, N) {
		if (!n[i])canbuild[i] = 1;
	}
	while (K--) {
		cin >> a >> b;
		if (a == 1) {
			if (!build(b)) {//이상한 빌드
				cout << "Lier!";
				return 0;
			}
		}
		else {
			if (!destroy(b)) {
				cout << "Lier!";
				return 0;
			}
		}
	}
	cout << "King-God-Emperor";
}