-
Notifications
You must be signed in to change notification settings - Fork 1
/
Dwarves.cpp
74 lines (57 loc) · 1.31 KB
/
Dwarves.cpp
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// A - Dwarves
// https://icpc.tum.de/content/contests/history/2016/gcpc_files/gcpc2016.pdf
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define D(x) cout << #x << " = " << (x) << endl;
bool cycle (int i, vector<vector<int>> &G, vector<int> &color) {
if (color[i] == 1) return true;
bool found = false;
if (color[i] == 0) {
color[i] = 1;
for (int j = 0; j < G[i].size(); ++j) {
found = cycle(G[i][j], G, color);
if (found) return found;
}
color[i] = 2;
}
return found;
}
int main() {
int n;
while (cin >> n) {
int mmx = 2 * n + 10;
vector<vector<int>> G(mmx);
vector<int> color(mmx, 0);
map<string, int> mapa;
int ind = 0;
for (int i = 0; i < n; ++i) {
string a, dir, b;
cin >> a >> dir >> b;
int u, v;
if (!mapa.count(a)) {
mapa[a] = ind ++;
}
u = mapa[a];
if (!mapa.count(b)) {
mapa[b] = ind ++;
}
v = mapa[b];
if (dir == ">")
G[u].push_back(v);
else
G[v].push_back(u);
}
int found = false;
for (int i = 0; i < mmx; ++i) {
if (color[i]) continue;
bool ans = cycle(i, G, color);
if (ans) {
found = true;
break;
}
}
cout << (found ? "impossible" : "possible") << endl;
}
return 0;
}