백준2099 The game of death

작성일 | In

문제 링크

  • http://icpc.me/2099

사용 알고리즘

  • 인접행렬 거듭제곱

시간복잡도

  • O(N3logK)

풀이

a가 b를 지목했다면 a에서 b로 가는 간선을 만들어줍니다.

a에서 시작해 k번 지목해서 b가 걸렸다는 것은, a에서 간선을 k개 타고 b에 도착한 것과 같습니다.
이런 경로의 존재 여부는 인접행렬 거듭제곱을 통해 쉽고 빠르게 알 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 988721597;

struct Matrix{
	int size;
	vector< vector<ll> > arr;
	Matrix(){size = 0;}
	Matrix(int n){
		size = n;
		arr = vector< vector<ll> >(n, vector<ll>(n));
	}
	Matrix operator * (const Matrix &x){
		Matrix ret(size);
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				for(int k=0; k<size; k++){
					ret.arr[i][j] += arr[i][k] * x.arr[k][j];
					ret.arr[i][j] %= mod;
				}
			}
		}
		return ret;
	}
};

Matrix powmat(Matrix a, ll b){
	if(b == 1) return a;
	Matrix ret = powmat(a, b/2);
	ret = ret * ret;
	if(b & 1) ret = ret * a;
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k, m; cin >> n >> k >> m;
	Matrix g(n);
	for(int i=0; i<n; i++){
		int a, b; cin >> a >> b;
		a--; b--;
		g.arr[i][a] = g.arr[i][b] = 1;
	}
	Matrix now = powmat(g, k);
	while(m--){
		int s, e; cin >> s >> e; s--; e--;
		if(now.arr[s][e] >= 1) cout << "death\n";
		else cout << "life\n";
	}
}