AT4831-[ABC155F] Perils in Parallel
题目:
题目描述:
AlDebaran 王国の侵攻によって、AtCoder 王国の各地に爆弾が仕掛けられてしまいました。
幸いにも AtCoder 王国 ABC 隊の健闘により制御装置の一部が手に入ったので、あなたはこれを使って解除を試みることにしました。
仕掛けられた爆弾は $ N $ 個あり、 $ 1 $ から $ N $ の番号がついています。爆弾 $ i $ は座標 $ A_i $ にあり、電源は $ B_i=1 $ のときオンに、 $ B_i=0 $ のときオフになっています。
制御装置には $ M $ 本のコードがあり、 $ 1 $ から $ M $ の番号がついています。コード $ j $ を切ると、座標が $ L_j $ 以上 $ R_j $ 以下の全ての爆弾の電源のオン・オフが切り替わります。
切るコードをうまく選ぶことで全ての爆弾の電源をオフにできるか判定し、できるならばそのようなコードの組合せを $ 1 $ つ出力してください。
After being invaded by the Kingdom of AlDebaran, bombs are planted throughout our country, AtCoder Kingdom.
Fortunately, our military team called ABC has managed to obtain a device that is a part of the system controlling the bombs.
There are $ N $ bombs, numbered $ 1 $ to $ N $ , planted in our country. Bomb $ i $ is planted at the coordinate $ A_i $ . It is currently activated if $ B_i=1 $ , and deactivated if $ B_i=0 $ .
The device has $ M $ cords numbered $ 1 $ to $ M $ . If we cut Cord $ j $ , the states of all the bombs planted between the coordinates $ L_j $ and $ R_j $ (inclusive) will be switched - from activated to deactivated, and vice versa.
Determine whether it is possible to deactivate all the bombs at the same time. If the answer is yes, output a set of cords that should be cut.
输入格式:
Input is given from Standard Input in the following format:
1
2
3
4
5
6
7
| $ N $ $ M $
$ A_1 $ $ B_1 $
$ : $
$ A_N $ $ B_N $
$ L_1 $ $ R_1 $
$ : $
$ L_M $ $ R_M $
|
输出格式:
If it is impossible to deactivate all the bombs at the same time, print -1. If it is possible to do so, print a set of cords that should be cut, as follows:
1
2
| $ k $
$ c_1 $ $ c_2 $ $ \dots $ $ c_k $
|
Here, $ k $ is the number of cords (possibly $ 0 $ ), and $ c_1,\ c_2,\ \dots,\ c_k $ represent the cords that should be cut. $ 1\ \leq\ c_1\ <\ c_2\ <\ \dots\ <\ c_k\ \leq\ M $ must hold.
样例:
样例输入1:
1
2
3
4
5
6
7
8
| 3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9
|
样例输出1:
样例输入2:
1
2
3
4
5
6
7
| 4 2
2 0
3 1
5 1
7 0
1 4
4 7
|
样例输出2:
样例输入3:
1
2
3
4
5
6
| 3 2
5 0
10 0
8 0
6 9
66 99
|
样例输出3:
样例输入4:
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
| 12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235
|
样例输出4:
样例输入5:
1
2
3
4
5
6
7
8
| 3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9
|
样例输出5:
样例输入6:
1
2
3
4
5
6
7
| 4 2
2 0
3 1
5 1
7 0
1 4
4 7
|
样例输出6:
样例输入7:
1
2
3
4
5
6
| 3 2
5 0
10 0
8 0
6 9
66 99
|
样例输出7:
样例输入8:
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
| 12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235
|
样例输出8:
思路:
实现:
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
| // Problem: AT4831 [ABC155F] Perils in Parallel
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT4831
// Memory Limit: 1000 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
typedef int ll;
const ll MAXN = 2e5 + 51;
struct Node
{
ll x, y;
inline bool operator<(const Node &rhs) const
{
return this->x < rhs.x;
}
};
struct Segment
{
ll l, r, id;
};
struct Edge
{
ll to, prev, id;
};
Node nd[MAXN];
Segment seg[MAXN];
Edge ed[MAXN << 1];
ll n, m, tot, cnt, l, r, lx, rx, flg, rr;
ll last[MAXN], res[MAXN], w[MAXN], c[MAXN], diff[MAXN], vis[MAXN];
inline void addEdge(ll from, ll to, ll id)
{
ed[++tot].prev = last[from];
ed[tot].to = to;
ed[tot].id = id;
last[from] = tot;
}
inline ll discrete(ll x)
{
ll l = 1, r = n + 1, res = 0, mid;
while (l <= r)
{
mid = (l + r) >> 1;
w[mid] >= x ? res = mid, r = mid - 1 : l = mid + 1;
}
return res;
}
inline ll discrete2(ll x)
{
ll l = 1, r = n, res = 0, mid;
while (l <= r)
{
mid = (l + r) >> 1;
w[mid] <= x ? res = mid, l = mid + 1 : r = mid - 1;
}
return res;
}
inline ll dfs(ll node, ll fa, ll x)
{
ll t = 0;
vis[node] = 1;
for (register int i = last[node]; i; i = ed[i].prev)
{
if (!vis[ed[i].to])
{
t ^= dfs(ed[i].to, node, i);
}
}
if (node == fa)
{
return t;
}
if (diff[node] ^ t)
{
res[++rr] = ed[x].id;
return 1;
}
return 0;
}
int main()
{
yin >> n >> m;
for (register int i = 1; i <= n; i++)
{
yin >> nd[i].x >> nd[i].y;
}
sort(nd + 1, nd + n + 1);
for (register int i = 1; i <= n; i++)
{
c[i] = nd[i].y, w[i] = nd[i].x;
}
for (register int i = 1; i <= m; i++)
{
yin >> lx >> rx;
l = discrete(lx), r = discrete2(rx);
if (rx < lx)
{
continue;
}
seg[++cnt] = (Segment){l, r, i};
}
for (register int i = 1; i <= n; i++)
{
diff[i] = c[i] ^ c[i - 1];
}
for (register int i = 1; i <= cnt; i++)
{
addEdge(seg[i].l, seg[i].r + 1, seg[i].id);
addEdge(seg[i].r + 1, seg[i].l, seg[i].id);
}
dfs(n + 1, n + 1, 0);
for (register int i = 1; i <= n; i++)
{
if (vis[i])
{
continue;
}
if (dfs(i, i, 0) != diff[i])
{
return puts("-1"), 0;
}
}
printf("%d\n", rr), sort(res + 1, res + rr + 1);
for (register int i = 1; i <= rr; i++)
{
printf("%d ", res[i]);
}
}
|