Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

CF GYM 102055B Balance of the Force 解题报告

有 $n$ 个骑士,每个骑士可以加入光阵营或暗阵营,并且获得一个力量,分别为 $L$ 和 $D$

现在有 $m$ 对骑士不能在同一个阵营,问力量差值(最大值和最小值的差值)最小是多少?如果不存在阵营满足仇恨骑士不在同一个阵营内,则输出IMPOSSIBLE。

$n,m \leq 10^5$

首先判断一下这张图是不是二分图,如果不是显然无解。

接下来我们考虑同一个联通块内答案显然只有两种,分别弄出来。

接下来的思路比较重要,到了这一步已经划归为一个类似偏序的问题,那我们显然先排序一下最大值,考虑最小值怎么搞

实际上变成了在一个范围内查询最小值,然后这个问题可以用线段树解决。

但是实际上这个题并不好写,又臭又长,写了三个小时左右

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define ri int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
ri v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}

const int N = 5e5 + 10;

vector <int> G[N];
int n,m,l[N],d[N],col[N],qwq,cnt,tot,pre[N],pos[N];
bool vis[N];

struct memb {
int minn,maxx,bel;
friend inline bool operator < (const memb &a1,const memb &a2) {
return a1.maxx < a2.maxx;
}
}a[N];

bool dfs1(int x,int c) {
col[x] = c;
for (auto y : G[x]) {
if (col[y] == c) return false;
if (!col[y] && !dfs1(y,3-c)) return false;
}
return 1;
}

bool check() {
for (int i = 1;i <= n;++i) {
if (!col[i]) {
if (!dfs1(i,1)) return false;
}
}
return 1;
}

void color(int x,int c,int las) {
//printf("%d %d %d\n",x,c,las);
col[x] = c;
//a[i] darkside/lightside a[i+1] lightside/darkside
if (las == 0) {
a[tot].minn = min(d[x],a[tot].minn);
a[tot].maxx = max(d[x],a[tot].maxx);
a[tot-1].minn = min(l[x],a[tot-1].minn);
a[tot-1].maxx = max(l[x],a[tot-1].maxx);
} else {
a[tot].minn = min(l[x],a[tot].minn);
a[tot].maxx = max(l[x],a[tot].maxx);
a[tot-1].minn = min(d[x],a[tot-1].minn);
a[tot-1].maxx = max(d[x],a[tot-1].maxx);
}
for (auto y : G[x]) {
if (!col[y]) color(y,c,las^1);
}
}

struct node {
int l,r,minn;
}tree[N<<2];

void build(int p,int l,int r) {
tree[p].l = l;tree[p].r = r;
if (l == r) {
tree[p].minn = 0x3f3f3f3f;
return ;
}
int mid = (l + r) >> 1;
build(p << 1,l,mid);
build(p << 1 | 1,mid + 1,r);
tree[p].minn = min(tree[p << 1].minn,tree[p<<1|1].minn);
return ;
}

void modify(int p,int x,int v) {
if (tree[p].l == tree[p].r ) {
tree[p].minn = v;
return ;
}
int mid = (tree[p].l + tree[p].r) >> 1;
if (x <= mid) modify(p<<1,x,v);
else modify(p<<1|1,x,v);
tree[p].minn = min(tree[p << 1].minn,tree[p<<1|1].minn);
return ;
}

void solve() {
printf("Case %d: ",qwq);
tot = cnt = 0;
read(n,m);
for (int i = 1;i <= n;++i) G[i].clear(),vis[i] = 0,pos[i] = 0;
for (int i = 1; i <= m;++i) {
int x,y;read(x,y);
G[x].push_back(y);G[y].push_back(x);
}
for (int i = 1;i <= n;++i) {
read(l[i],d[i]);
col[i] = 0;
}
if (!check()) {
puts("IMPOSSIBLE");
return ;
}
for (int i = 1;i <= n;++i) col[i] = 0;
for (int i = 1;i <= n;++i) {
if (!col[i]) {
tot += 2;
a[tot].minn = 0x3f3f3f3f,a[tot].maxx = -0x3f3f3f3f;
a[tot-1].minn = 0x3f3f3f3f,a[tot-1].maxx = -0x3f3f3f3f;
a[tot].bel = a[tot-1].bel = ++cnt;
color(i,cnt,0);
}
//printf("%d:%d\n",i,col[i]);
}//calc every CC
//puts("part1");
sort(a+1,a+tot+1);
/*for (int i = 1;i <= tot;++i) {
printf("%d %d %d\n",a[i].minn,a[i].maxx,a[i].bel);
}*/
pre[0] = 0;
for (int i = 1;i <= tot;++i) {
pre[i] = pre[i-1];
if (!vis[a[i].bel]) {
pre[i]++;vis[a[i].bel] = 1;
}
}//sort and calc every CC
//puts("part2");
build(1,1,tot);
//puts("part3");
int curmax,curmin = 0x3f3f3f3f;
int ans = 0x3f3f3f3f;
for (int i = 1;i <= tot;++i) {
//printf("%d ",pre[i]);
curmax = a[i].maxx,curmin = a[i].minn;
if (pre[i] == cnt) {
if (pos[a[i].bel]) {
modify(1,pos[a[i].bel],0x3f3f3f3f);
}
curmin = min(curmin,tree[1].minn);
//printf("%d %d\n",curmin,i);
ans = min(ans,curmax - curmin);
}
if (pos[a[i].bel]) {
int tmp = max(a[i].minn,a[pos[a[i].bel]].minn);
modify(1,pos[a[i].bel],tmp);
modify(1,i,tmp);
} else {
pos[a[i].bel] = i;
modify(1,i,a[i].minn);
}
// puts("part4");
}//for every max num,find a closest num to fix it
printf("%d\n",ans);
}

signed main() {
int T;read(T);
for (qwq = 1;qwq <= T;++qwq) solve();
return 0;
}