QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#610100#9412. Stop the CastleKanate#AC ✓61ms74120kbC++144.9kb2024-10-04 14:55:412024-10-04 14:55:41

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 14:55:41]
  • 评测
  • 测评结果:AC
  • 用时:61ms
  • 内存:74120kb
  • [2024-10-04 14:55:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define int long long
const int INF = 1e9 + 7;
const int M = 3e6 + 7;
const int N = 3e6+ 7;
int n , m , s , t , cnt =1 ;
int T;
int lv[N],cur[N];
struct edge{
	int v , nex , flow;
}e[M];int head[N];
int X[N],Y[N];
int fx[N],fy[N];
bool bfs(){
	memset(lv,-1,sizeof lv);
	lv[s] = 0 ;
	memcpy(cur,head,sizeof cur);
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i = head[x];i;i = e[i].nex){
			int v = e[i].v;
			int val = e[i].flow;
			if(val > 0 && lv[v] == -1){
				lv[v] = lv[x] + 1;
				q.push(v);
			}
		}
	}
	return lv[t] != -1;
}

int dfs(int x=s,int flow = INF){
	if(x==t) return flow;
	int rmn = flow;
	for(int i=cur[x];i && rmn;i=e[i].nex){
		cur[x] = i;
		int v = e[i].v;
		int val = e[i].flow;
		if(val > 0 && lv[v] == lv[x] + 1){
			int c = dfs(v,min(val,rmn));
			rmn -= c;
			e[i].flow -= c;
			e[i^1].flow += c;
		}
	}
	return flow - rmn;
}
void add(int u,int v,int flow){
	e[++cnt].v = v;
	e[cnt].nex = head[u];
	head[u] = cnt;
	e[cnt].flow = flow;
}
void add_edge(int u,int v,int flow){
	//cout <<"ADD " << u << " " << v << " " << flow << endl;
	add(u,v,flow);
	add(v,u,0);
}
vector<int>h,r;
unordered_map<int,int> recal_R;
unordered_map<int,int> recal_H;
int pd[2001][2001];
int id[2001][2001];
struct wqweqweq{
	int x , y;
}qwq[M];
int mx,my;
int tot = 0 ;
int GET_id(int x,int y){
	return (x-1) * (my+1) + y;
}

void print(){
			for(int i=1;i<=mx;i++){
			int las = - 1;
			for(int j=1;j<=my;j++){
				if(pd[i][j] == 1) {
 					if(las == -1) las = j;
					else {
 						pd[i][j-1] = 3; 
						las = j;
					}
				}
				if(pd[i][j] == 2 || pd[i][j] == 3){
					las = -1;
				} 
			}
		}
		for(int j = 1;j<=my;j++){
			int las = - 1;
			for(int i=1;i<=mx;i++){
				if(pd[i][j] == 1){
					if(las==-1) las = i;
					else {
						pd[i-1][j] = 3; 
						las = i;
					}
				}
				if(pd[i][j] == 2 || pd[i][j] == 3){
					las = -1;
				} 
			}
		}
	for(int i=1;i<=mx;i++)
	for(int j=1;j<=my;j++)
	if(pd[i][j] == 3){
		cout << h[i-1] << " " << r[j-1] << endl;
	}
}
map<pair<int,int>,pair<int,int>>nowmp;
void solve(){
	nowmp.clear();
		int ans = 0 ;
		for(int i=1;i<=mx;i++){
			int las = - 1;
			for(int j=1;j<=my;j++){
				if(pd[i][j] == 1) {
 					if(las == -1) las = j;
					else {
						if(r[las-1]+1 == r[j-1]){
							cout << -1 << endl;
							return ;
						}
						++ tot;
						qwq[tot] = {i,j};
						ans ++ ;
						for(int k= las+1;k<=j-1;k++) id[i][k] = tot;
						add_edge(0,tot,1);
						las = j;
					}
				}
				if(pd[i][j] == 2){
					las = -1;
				} 
			}
		}
		t = ++ tot;
		for(int j = 1;j<=my;j++){
			int las = - 1;
			for(int i=1;i<=mx;i++){
				if(pd[i][j] == 1){
					if(las==-1) las = i;
					else {
						if(h[las-1]+1 == h[i-1]) {
							cout << -1 << endl;
							return ;
						}
						++ tot;
						ans ++ ;
						for(int k=las+1;k<=i-1;k++) 
						if(id[k][j]){
							add_edge(id[k][j],tot,1);
							nowmp[make_pair(id[k][j],tot)] = make_pair(k,j);
						}
						add_edge(tot,t,1);
						las = i;
					}
				}
				if(pd[i][j] == 2){
					las = - 1;
				}
			}
		}
	while(bfs()){
	//	cout << ans << endl;
		ans -= dfs();
	}
	for(int i = head[0];i;i=e[i].nex) {
		int v = e[i].v;
		for(int j=head[v];j;j=e[j].nex){
			int w = e[j].v;
			if(w==0 || e[j].flow==1) continue;
			pair<int,int> nod = nowmp[make_pair(v,w)];
			pd[nod.first][nod.second] = 3;
		}
	}

	cout << ans << endl;
	print();


	//cout << ans << endl;
}

void clear(){
	for(int i=0;i<=tot;i++) head[i]  = 0 ;
	for(int i=1;i<=mx;i++)
	for(int j=1;j<=my;j++)
	pd[i][j] = id[i][j] = 0 ;
	tot =  0;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T-->0){
		cin >> n ;
		h.clear();recal_R.clear();
		r.clear();recal_H.clear();cnt = 1;
		mx = my = 0 ;
		for(int i=1;i<=n;i++){
			int x , y;
			cin >> x >> y;
			X[i] = x;
			Y[i] = y; 
			h.emplace_back(x);
			r.emplace_back(y);
		}
		cin >> m;
		for(int i=1;i<=m;i++){
			cin >> fx[i] >> fy[i];
			h.emplace_back(fx[i]);
			r.emplace_back(fy[i]);
		}
		sort(h.begin(),h.end());
		sort(r.begin(),r.end());
		r.resize(unique(r.begin(),r.end())-r.begin());
		h.resize(unique(h.begin(),h.end())-h.begin());
		int rs = (int)r.size() - 1;
		int hs = (int)h.size() - 1;
		for(int i=0;i<rs;i++) 
		if(r[i]+1 != r[i+1]) r.emplace_back(r[i]+1);
		for(int i=0;i<hs;i++) 
		if(h[i]+1 != h[i+1]) h.emplace_back(h[i]+1);
		sort(h.begin(),h.end());
		sort(r.begin(),r.end());
		for(int i=0;i<r.size();i++)
			recal_R[r[i]]  = i+1;
		my = (int)r.size()  ;
		for(int i=0;i<h.size();i++)
			recal_H[h[i]]  = i+1;

		
		mx = (int)h.size() ;

		for(int i=1;i<=n;i++)
			pd [recal_H[X[i]]][recal_R[Y[i]]] = 1;
		for(int i=1;i<=m;i++)
			pd [recal_H[fx[i]]][recal_R[fy[i]]] = 2;
		solve();
		clear();
	}
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 20ms
memory: 66652kb

input:

4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0

output:

2
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 51ms
memory: 64768kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
29 12
41 18
42 38
5
16 13
16 47
26 26
31 6
36 50
0
1
42 10
0
1
43 31
5
1 10
1 38
33 47
43 44
44 46
0
5
10 1
27 41
29 40
30 15
44 35
1
32 12
0
0
0
0
6
12 40
23 10
23 45
29 33
34 46
35 34
0
3
20 31
34 17
43 32
0
-1
3
16 36
25 8
29 39
6
5 5
6 6
7 5
8 11
9 9
10 10

result:

ok ok 21 cases (21 test cases)

Test #3:

score: 0
Accepted
time: 28ms
memory: 74120kb

input:

2
200
7 52
9 160
10 4
12 61
18 436
19 430
20 499
24 139
25 416
29 53
33 153
35 275
35 310
37 25
38 477
39 349
42 120
44 158
45 330
49 486
50 204
51 67
52 138
52 305
56 139
63 132
66 4
67 327
70 484
71 67
72 308
74 218
76 479
81 139
82 90
86 201
87 335
91 35
91 220
92 496
94 29
94 436
96 359
97 299
1...

output:

46
35 309
52 139
64 4
70 67
77 139
91 160
93 436
94 35
98 499
126 61
126 300
132 67
138 429
143 25
147 477
154 138
154 496
185 147
187 446
187 467
199 432
224 153
224 431
260 275
261 491
270 305
274 110
277 270
277 356
278 186
288 272
302 367
306 374
311 186
311 481
333 177
334 367
349 61
350 35
352...

result:

ok ok 2 cases (2 test cases)

Test #4:

score: 0
Accepted
time: 58ms
memory: 65436kb

input:

20
13
89287395 441913071
89287395 590314987
142917372 582720391
142917372 598813561
232930851 582720391
263974835 468188689
263974835 490702144
543529670 152471388
543529670 219371706
647691663 598813561
772865038 598813561
773363571 482933265
773363571 561453301
8
128947560 120560639
264980960 4742...

output:

8
89287395 582720392
142917372 590314988
142917373 582720391
263974835 482933266
543529670 152471389
550434846 598813561
647691664 598813561
773363571 490702145
7
118192020 358274214
183418804 871951216
794031083 762966373
808969359 728848950
808969359 818037531
808969359 914645537
808969360 3547113...

result:

ok ok 20 cases (20 test cases)

Test #5:

score: 0
Accepted
time: 24ms
memory: 71080kb

input:

2
184
35763790 435860426
152681166 443483111
261932524 745277126
261932524 787982418
314305867 342102981
314305867 522593781
314305867 747023891
314305867 811404535
314305867 816914009
314305867 857896659
319901983 797458033
321347896 342102981
332550928 902179526
343207116 914408792
350635050 15515...

output:

160
261932524 773080211
314305867 513614219
314305867 745277127
314305867 787982418
314305867 815487778
314305867 857742165
319901984 342102981
343207117 342102981
343207117 857896659
350635050 335551846
350635050 421876107
350635050 435860426
350635050 773080211
350635050 811404535
350635050 857742...

result:

ok ok 2 cases (2 test cases)

Test #6:

score: 0
Accepted
time: 21ms
memory: 71040kb

input:

2
193
78368109 329329995
87932514 657474465
87932514 903492853
94608574 845872655
103602204 88649154
124431127 405860533
145262472 108198774
145262472 907127202
154400439 136367504
165270984 773451933
184157521 409828915
197728547 291882089
197728547 609623645
211750768 843867422
246178069 108396139...

output:

145
87932514 899831819
145262472 903492853
197728547 409828915
246178069 291882089
291242118 564718673
355443170 88649154
355443170 211732513
365329221 29599938
365329221 79866983
365329221 108887130
365329221 136367504
365329221 196991277
365329221 211655411
365329221 211732514
365329221 245960659
...

result:

ok ok 2 cases (2 test cases)

Test #7:

score: 0
Accepted
time: 28ms
memory: 71448kb

input:

2
192
1075648 579875717
1075648 937648715
1393060 191616432
3957616 541362608
3957616 971879257
5415801 541362608
5887448 541362608
5887448 624842533
25767120 610618164
26193206 214214028
26193206 231445627
26727662 374314271
29550509 755417826
29550509 917592925
30033126 610618164
31134588 58188305...

output:

131
1075648 934726176
3957616 970791332
3957617 541362608
5415802 541362608
5887448 624100258
26193206 230646833
29550509 917208988
29550510 610618164
30033127 755417826
31134588 191616433
31134588 231445627
31134589 755417826
33207011 541362608
46425938 755417826
77658794 231445627
133595743 278558...

result:

ok ok 2 cases (2 test cases)

Test #8:

score: 0
Accepted
time: 61ms
memory: 65024kb

input:

20
14
378192988 147499872
378192988 837331700
449924898 147499872
449924898 837331700
592684636 147499872
592684636 837331700
783332532 147499872
783332532 837331700
378192988 197547597
783332532 197547597
378192988 343857831
783332532 343857831
378192988 576579017
783332532 576579017
2
449924898 19...

output:

15
378192988 147499873
378192988 197547598
378192988 343857832
378192988 576579018
378192989 147499872
378192989 837331700
449924899 147499872
449924899 837331700
592684637 147499872
592684637 576579017
592684637 837331700
783332532 147499873
783332532 197547598
783332532 343857832
783332532 5765790...

result:

ok ok 20 cases (20 test cases)

Test #9:

score: 0
Accepted
time: 8ms
memory: 70720kb

input:

2
200
8623893 3649468
8623893 989134714
24820918 3649468
24820918 989134714
43705451 3649468
43705451 989134714
45500146 3649468
45500146 989134714
58265855 3649468
58265855 989134714
112263159 3649468
112263159 989134714
126496650 3649468
126496650 989134714
137574156 3649468
137574156 989134714
14...

output:

249
8623893 3649469
8623893 6255308
8623893 11610915
8623893 23366505
8623893 28938722
8623893 31914493
8623893 36029446
8623893 66226936
8623893 84152869
8623893 132710905
8623893 149083020
8623893 174305882
8623893 180413074
8623893 195080122
8623893 231772825
8623893 234663337
8623893 246352595
8...

result:

ok ok 2 cases (2 test cases)

Test #10:

score: 0
Accepted
time: 15ms
memory: 67400kb

input:

2
200
2691939 27674656
2691939 984614319
30225807 27674656
30225807 984614319
39388076 27674656
39388076 984614319
55883389 27674656
55883389 984614319
77258752 27674656
77258752 984614319
106874917 27674656
106874917 984614319
144383292 27674656
144383292 984614319
145360776 27674656
145360776 9846...

output:

216
2691939 27674657
2691939 69029841
2691939 160188719
2691939 176264535
2691939 189367595
2691939 206375959
2691939 234369847
2691939 243902653
2691939 257900117
2691939 268022575
2691939 293316180
2691939 294444587
2691939 363531957
2691939 376231504
2691939 383623457
2691939 386906491
2691939 39...

result:

ok ok 2 cases (2 test cases)

Test #11:

score: 0
Accepted
time: 4ms
memory: 69304kb

input:

2
200
1005937 7
3412691 7
5764908 7
7897785 7
8061992 7
12801501 7
18529696 7
22574605 7
25203351 7
34574958 7
34998216 7
40928451 7
49792193 7
55962320 7
59632864 7
62353373 7
62611196 7
65346591 7
71459320 7
71550121 7
72215989 7
82584263 7
86119549 7
96204862 7
96940713 7
97693112 7
102067050 7
1...

output:

199
1005938 7
3412692 7
5764909 7
7897786 7
8061993 7
12801502 7
18529697 7
22574606 7
25203352 7
34574959 7
34998217 7
40928452 7
49792194 7
55962321 7
59632865 7
62353374 7
62611197 7
65346592 7
71459321 7
71550122 7
72215990 7
82584264 7
86119550 7
96204863 7
96940714 7
97693113 7
102067051 7
105...

result:

ok ok 2 cases (2 test cases)

Extra Test:

score: 0
Extra Test Passed