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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#include <stack>
#include <algorithm>
const int MAXN = 1005;
const int MAXM = 505;
struct ;
struct Node {
Edge *e;
int dfn, low, belong;
bool ins;
} N[MAXM << 1];
struct {
Node *u, *v;
Edge *next;
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
};
void addEdge(int u, int v) {
N[u].e = new Edge(&N[u], &N[v]);
}
int getV(int x, int k){
return (x << 1) - k;
}
struct TwoSat {
std::stack<Node *> s;
int dfsClock, sccCnt;
void tarjan(Node *u) {
s.push(u);
u->dfn = u->low = ++dfsClock;
u->ins = true;
for (Edge *e = u->e; e; e = e->next) {
if (e->v->dfn == 0) {
tarjan(e->v);
u->low = std::min(u->low, e->v->low);
} else if (e->v->ins) u->low = std::min(u->low, e->v->dfn);
}
if (u->dfn == u->low) {
Node *c;
sccCnt++;
while (true) {
c = s.top();
s.pop();
c->ins = false;
c->belong = sccCnt;
if (c == u) break;
}
}
}
bool check(int n) {
for (int i = 1; i <= n; i++)
if (N[getV(i, 0)].belong == N[(getV(i, 1))].belong) return false;
return true;
}
bool operator()(int n) {
dfsClock = sccCnt = 0;
for (int i = 1; i <= n << 1; i++) if (N[i].dfn == 0) tarjan(&N[i]);
return check(n);
}
} ts;
struct Pair {
int u, v;
Pair() {}
Pair(int u, int v) : u(u), v(v) {}
} E[MAXM];
bool cross(const Pair &a, const Pair &b) {
return (a.u < b.u && b.u < a.v && a.v < b.v) ||
(b.u < a.u && a.u < b.v && b.v < a.v);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int top = 0;
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
if (u > v) std::swap(u, v);
if (v - u <= 1 || (u == 0 && v == n - 1)) continue;
E[++top] = Pair(u, v);
}
m = top;
for (int i = 1; i <= m; i++) for (int j = i + 1; j <= m; j++) {
if (cross(E[i], E[j])) {
addEdge(getV(i, 0), getV(j, 1));
addEdge(getV(i, 1), getV(j, 0));
addEdge(getV(j, 0), getV(i, 1));
addEdge(getV(j, 1), getV(i, 0));
}
}
puts(ts(m) ? "panda is telling the truth..." : "the evil panda is lying again");
return 0;
}
|
近期评论