QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#781638#8892. Power GridDaiRuiChen00723 107ms31996kbC++172.5kb2024-11-25 16:43:402024-11-25 16:44:07

Judging History

This is the latest submission verdict.

  • [2024-11-25 16:44:07]
  • Judged
  • Verdict: 23
  • Time: 107ms
  • Memory: 31996kb
  • [2024-11-25 16:43:40]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1005;
int n,m,a[MAXN][MAXN],rid[MAXN][2],cid[MAXN][2];
vector <int> G[MAXN*4];
int low[MAXN*4],dfn[MAXN*4],dcnt,stk[MAXN*4],tp,bel[MAXN*4],scnt;
bool ins[MAXN*4];
void tarjan(int u) {
	low[u]=dfn[u]=++dcnt,stk[++tp]=u,ins[u]=true;
	for(int v:G[u]) {
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) {
		++scnt;
		while(ins[u]) bel[stk[tp]]=scnt,ins[stk[tp--]]=false;
	}
}
int x[MAXN],y[MAXN];
signed main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>a[i][j];
	int tot=0;
	for(int i=2;i<=n;++i) rid[i][0]=++tot;
	for(int i=2;i<=m;++i) cid[i][0]=++tot;
	for(int i=2;i<=n;++i) rid[i][1]=++tot;
	for(int i=2;i<=m;++i) cid[i][1]=++tot;
	for(int i=2;i<=n;++i) for(int j=2;j<=m;++j) {
		for(int tx:{1,-1}) for(int ty:{1,-1}) {
			if(abs(tx*a[i][1]+ty*a[1][j]-a[1][1])!=a[i][j]) {
				int u=(tx==1),v=(ty==1);
				G[rid[i][u]].push_back(cid[j][v^1]);
				G[cid[j][v]].push_back(rid[i][u^1]);
//				cerr<<"ban("<<i<<","<<j<<") = "<<tx<<" "<<ty<<"\n";
				//ban (x,y)
			}
		}
	}
	for(int i=1;i<=tot;++i) if(!dfn[i]) tarjan(i);
//	for(int i=1;i<=tot;++i) {
//		cerr<<"u = "<<i<<": ";
//		for(int j:G[i]) cerr<<j<<" ";
//		cerr<<"\n";
//	}
//	for(int i=1;i<=tot;++i) cerr<<bel[i]<<" \n"[i==tot];
	for(int i=2;i<=n;++i) {
		assert(bel[rid[i][0]]!=bel[rid[i][1]]);
		if(bel[rid[i][0]]<bel[rid[i][1]]) a[i][1]*=-1;
	}
	for(int i=2;i<=m;++i) {
		assert(bel[cid[i][0]]!=bel[cid[i][1]]);
		if(bel[cid[i][0]]<bel[cid[i][1]]) a[1][i]*=-1;
	}
	for(int i=2;i<=n;++i) for(int j=2;j<=m;++j) {
		a[i][j]=a[i][1]+a[1][j]-a[1][1];
	}
//	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cerr<<a[i][j]<<" \n"[j==m];
	x[1]=0;
	for(int j=1;j<=m;++j) y[j]=x[1]-a[1][j];
	for(int i=2;i<=n;++i) x[i]=y[1]+a[i][1];
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) assert(a[i][j]==x[i]-y[j]);
	ll sx=0,sy=0;
	for(int i=1;i<=n;++i) sx+=x[i];
	for(int j=1;j<=m;++j) sy+=y[j];
	if(n==m) assert(sx==sy);
	else assert((sx-sy)%(n-m)==0);
	if(n!=m) {
		ll k=(sx-sy)/(m-n);
		for(int i=1;i<=n;++i) x[i]+=k;
		for(int j=1;j<=m;++j) y[j]+=k;
	}
	sx=0,sy=0;
	for(int i=1;i<=n;++i) sx+=x[i];
	for(int j=1;j<=m;++j) sy+=y[j];
	assert(sx==sy);
	memset(a,0,sizeof(a));
	for(int i=2;i<=n;++i) a[i][1]=x[i];
	for(int j=2;j<=m;++j) a[1][j]=y[j];
	a[1][1]=x[1]+y[1]-sx;
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cout<<a[i][j]<<" \n"[j==m];
	return 0;
}

详细

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 1ms
memory: 7640kb

input:

1 1
0

output:

0

result:

ok correct

Test #2:

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

input:

1 1
0

output:

0

result:

ok correct

Test #3:

score: 8
Accepted
time: 1ms
memory: 7664kb

input:

1 2
1 1

output:

-1 1

result:

ok correct

Test #4:

score: 8
Accepted
time: 1ms
memory: 7728kb

input:

3 1
0
3
1

output:

2
-1
1

result:

ok correct

Test #5:

score: 8
Accepted
time: 1ms
memory: 7664kb

input:

2 2
1 1
1 1

output:

1 -1
-2 0

result:

ok correct

Test #6:

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

input:

3 3
2 1 1
2 1 1
0 1 3

output:

0 -1 1
0 0 0
-2 0 0

result:

ok correct

Test #7:

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

input:

3 3
0 1 0
2 1 2
1 2 1

output:

1 -1 0
-2 0 0
1 0 0

result:

ok correct

Test #8:

score: 8
Accepted
time: 1ms
memory: 7776kb

input:

3 3
0 0 2
2 2 0
0 0 2

output:

2 0 -2
-2 0 0
0 0 0

result:

ok correct

Test #9:

score: 8
Accepted
time: 1ms
memory: 7620kb

input:

3 3
3 1 2
3 1 2
3 1 2

output:

-3 1 2
0 0 0
0 0 0

result:

ok correct

Test #10:

score: 8
Accepted
time: 1ms
memory: 7720kb

input:

3 3
3 3 3
0 0 0
3 3 3

output:

6 -3 -3
-3 0 0
-6 0 0

result:

ok correct

Subtask #2:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #11:

score: 0
Runtime Error

input:

1 6
1 0 3 1 3 0

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #23:

score: 11
Accepted
time: 1ms
memory: 7712kb

input:

1 1
0

output:

0

result:

ok correct

Test #24:

score: 0
Runtime Error

input:

1 10
230 289 918 752 224 184 573 217 398 715

output:


result:


Subtask #4:

score: 0
Runtime Error

Test #30:

score: 6
Accepted
time: 0ms
memory: 7660kb

input:

2 2
0 0
0 0

output:

0 0
0 0

result:

ok correct

Test #31:

score: 6
Accepted
time: 0ms
memory: 7728kb

input:

2 2
7 7
7 7

output:

7 -7
-14 0

result:

ok correct

Test #32:

score: 6
Accepted
time: 1ms
memory: 7664kb

input:

2 4
7 7 7 7
7 7 7 7

output:

7 0 0 0
-7 0 0 0

result:

ok correct

Test #33:

score: 6
Accepted
time: 0ms
memory: 7688kb

input:

20 40
80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80
80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80
80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 ...

output:

2816 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72 -72
-152 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-152 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

result:

ok correct

Test #34:

score: 6
Accepted
time: 1ms
memory: 7756kb

input:

20 40
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

352 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9
-19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-19 0 0 0 0 0 0...

result:

ok correct

Test #35:

score: 0
Runtime Error

input:

1000 1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...

output:


result:


Subtask #5:

score: 15
Accepted

Test #46:

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

input:

2 4
253 431 207 483
243 65 289 13

output:

243 8 232 -44
-57 0 0 0

result:

ok correct

Test #47:

score: 15
Accepted
time: 1ms
memory: 7660kb

input:

2 4
188 566 555 176
471 283 272 459

output:

-471 329 318 -413
46 0 0 0

result:

ok correct

Test #48:

score: 15
Accepted
time: 1ms
memory: 7728kb

input:

5 6
39 93 668 330 117 610
13 145 720 382 65 662
417 285 290 48 495 232
210 78 497 159 288 439
813 681 106 444 891 164

output:

-488 -181 394 56 -391 336
-326 0 0 0 0 0
104 0 0 0 0 0
-103 0 0 0 0 0
500 0 0 0 0 0

result:

ok correct

Test #49:

score: 15
Accepted
time: 1ms
memory: 7664kb

input:

4 7
330 140 57 520 147 685 359
70 540 457 120 547 285 41
168 638 555 22 645 187 139
425 45 38 615 52 780 454

output:

-25 389 306 -271 396 -436 -110
-151 0 0 0 0 0 0
-249 0 0 0 0 0 0
344 0 0 0 0 0 0

result:

ok correct

Test #50:

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

input:

10 10
853 399 803 868 626 195 356 314 232 136
409 45 359 424 182 249 88 130 212 308
134 320 84 149 93 524 363 405 487 583
60 394 10 75 167 598 437 479 561 657
50 404 0 65 177 608 447 489 571 667
828 374 778 843 601 170 331 289 207 111
457 3 407 472 230 201 40 82 164 260
34 420 16 49 193 624 463 505 ...

output:

3929 -399 -803 -868 -626 -195 -356 -314 -232 -136
-444 0 0 0 0 0 0 0 0 0
-719 0 0 0 0 0 0 0 0 0
-793 0 0 0 0 0 0 0 0 0
-803 0 0 0 0 0 0 0 0 0
-25 0 0 0 0 0 0 0 0 0
-396 0 0 0 0 0 0 0 0 0
-819 0 0 0 0 0 0 0 0 0
-323 0 0 0 0 0 0 0 0 0
-460 0 0 0 0 0 0 0 0 0

result:

ok correct

Test #51:

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

input:

10 10
376 557 253 418 586 309 363 261 20 193
343 524 220 385 553 276 330 228 53 160
322 141 445 280 112 389 335 437 718 505
123 58 246 81 87 190 136 238 519 306
39 142 162 3 171 106 52 154 435 222
6 175 129 36 204 73 19 121 402 189
297 478 174 339 507 230 284 182 99 114
441 260 564 399 231 508 454 5...

output:

2920 -557 -253 -418 -586 -309 -363 -261 20 -193
-33 0 0 0 0 0 0 0 0 0
-698 0 0 0 0 0 0 0 0 0
-499 0 0 0 0 0 0 0 0 0
-415 0 0 0 0 0 0 0 0 0
-382 0 0 0 0 0 0 0 0 0
-79 0 0 0 0 0 0 0 0 0
-817 0 0 0 0 0 0 0 0 0
-346 0 0 0 0 0 0 0 0 0
-27 0 0 0 0 0 0 0 0 0

result:

ok correct

Test #52:

score: 15
Accepted
time: 1ms
memory: 7744kb

input:

10 10
608 306 681 555 168 504 161 276 342 308
236 66 309 183 204 132 211 96 30 64
589 287 662 536 149 485 142 257 323 289
70 372 3 123 510 174 517 402 336 370
160 462 87 213 600 264 607 492 426 460
178 124 251 125 262 74 269 154 88 122
458 156 531 405 18 354 11 126 192 158
61 241 134 8 379 43 386 27...

output:

3301 -306 -681 -555 -168 -504 -161 -276 -342 -308
-372 0 0 0 0 0 0 0 0 0
-19 0 0 0 0 0 0 0 0 0
-678 0 0 0 0 0 0 0 0 0
-768 0 0 0 0 0 0 0 0 0
-430 0 0 0 0 0 0 0 0 0
-150 0 0 0 0 0 0 0 0 0
-547 0 0 0 0 0 0 0 0 0
-719 0 0 0 0 0 0 0 0 0
-226 0 0 0 0 0 0 0 0 0

result:

ok correct

Test #53:

score: 15
Accepted
time: 1ms
memory: 7736kb

input:

2 4
1 2 3 4
5 6 7 8

output:

-5 5 4 3
11 0 0 0

result:

ok correct

Test #54:

score: 15
Accepted
time: 1ms
memory: 7736kb

input:

10 20
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
10...

output:

-1789 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91
131 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
151 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
171 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
191 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
211 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
231 0 0 0 0 0 0 0...

result:

ok correct

Test #55:

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

input:

21 42
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 10...

output:

-17618 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 421
505 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
547 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

result:

ok correct

Test #56:

score: 15
Accepted
time: 1ms
memory: 7784kb

input:

8 11
350 680 125 424 555 68 443 319 540 709 71
170 160 395 96 35 452 77 201 20 189 449
121 451 104 195 326 161 214 90 311 480 158
322 8 547 248 117 604 229 353 132 37 601
156 174 381 82 49 438 63 187 34 203 435
251 581 26 325 456 31 344 220 441 610 28
513 183 738 439 308 795 420 544 323 154 792
116 ...

output:

451 -293 262 -37 -168 319 -56 68 -153 -322 316
-133 0 0 0 0 0 0 0 0 0 0
158 0 0 0 0 0 0 0 0 0 0
-285 0 0 0 0 0 0 0 0 0 0
-119 0 0 0 0 0 0 0 0 0 0
288 0 0 0 0 0 0 0 0 0 0
-476 0 0 0 0 0 0 0 0 0 0
153 0 0 0 0 0 0 0 0 0 0

result:

ok correct

Test #57:

score: 15
Accepted
time: 1ms
memory: 7724kb

input:

15 5
148 610 23 697 750
176 286 301 373 426
528 66 653 21 74
64 526 61 613 666
133 595 8 682 735
122 584 3 671 724
637 175 762 88 35
196 266 321 353 406
607 145 732 58 5
87 375 212 462 515
234 696 109 783 836
484 22 609 65 118
495 33 620 54 107
598 136 723 49 4
421 41 546 128 181

output:

1024 -258 329 -345 -398
28 0 0 0 0
-324 0 0 0 0
268 0 0 0 0
337 0 0 0 0
326 0 0 0 0
-433 0 0 0 0
8 0 0 0 0
-403 0 0 0 0
117 0 0 0 0
438 0 0 0 0
-280 0 0 0 0
-291 0 0 0 0
-394 0 0 0 0
-217 0 0 0 0

result:

ok correct

Subtask #6:

score: 0
Runtime Error

Test #58:

score: 5
Accepted
time: 85ms
memory: 20052kb

input:

1000 1000
1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 ...

output:

495 0 0 -1 0 -1 0 -1 0 0 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 -1 0 -1 -1 0 -1 -1 0 -1 -1 -1 0 0 -1 -1 0 0 0 -1 -1 0 -1 -1 0 -1 -1 -1 0 0 0 -1 0 0 0 -1 0 -1 -1 0 0 0 -1 0 0 0 -1 -1 0 -1 -1 0 0 0 0 -1 0 -1 -1 0 0 0 0 0 -1 0 -1 -1 0 0 -1 -1 0 -1 0 -1 -1 -1 -1 0 -1 -1 0 0 -1 0 -1 0 -1 -1 0 -1 0 0 0 0...

result:

ok correct

Test #59:

score: 0
Runtime Error

input:

1000 1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:


result:


Subtask #7:

score: 0
Runtime Error

Test #68:

score: 15
Accepted
time: 2ms
memory: 7664kb

input:

2 2
5 52
52 5

output:

52 -52
-57 0

result:

ok correct

Test #69:

score: 15
Accepted
time: 103ms
memory: 31848kb

input:

1000 1000
640 423 797 825 85 491 146 594 713 894 923 193 511 700 556 269 32 177 29 16 394 971 754 194 930 404 686 794 19 267 410 880 859 52 477 347 94 826 638 132 385 628 642 795 332 98 606 377 681 330 731 339 157 855 875 836 450 46 225 661 138 909 917 873 371 223 152 19 44 67 792 3 466 740 151 681 ...

output:

474948 -423 -797 -825 -85 -491 -146 -594 -713 -894 -923 -193 -511 -700 -556 -269 -32 -177 -29 -16 -394 -971 -754 -194 -930 -404 -686 -794 19 -267 -410 -880 -859 -52 -477 -347 -94 -826 -638 -132 -385 -628 -642 -795 -332 -98 -606 -377 -681 -330 -731 -339 -157 -855 -875 -836 -450 -46 -225 -661 -138 -90...

result:

ok correct

Test #70:

score: 15
Accepted
time: 107ms
memory: 31996kb

input:

1000 1000
26 347 442 93 41 633 378 574 17 254 45 40 505 163 309 257 90 394 74 555 350 496 602 5 228 40 317 266 78 175 172 417 290 129 633 6 601 530 24 500 522 201 391 82 557 123 248 614 204 249 165 58 567 458 340 142 180 544 61 39 498 633 551 273 167 225 469 88 131 4 221 218 470 520 59 209 276 365 1...

output:

-137450 -347 442 93 41 633 378 574 17 -254 -45 40 505 -163 309 257 90 394 74 555 -350 496 602 -5 -228 40 -317 -266 78 -175 172 417 290 129 633 -6 601 530 24 500 522 201 391 82 557 123 -248 614 204 249 165 -58 567 458 -340 -142 -180 544 -61 39 498 633 551 -273 167 225 469 -88 131 -4 221 -218 470 520 ...

result:

ok correct

Test #71:

score: 0
Runtime Error

input:

1000 1000
177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 17...

output:


result:


Subtask #8:

score: 0
Skipped

Dependency #2:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%