QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#781638 | #8892. Power Grid | DaiRuiChen007 | 23 | 107ms | 31996kb | C++17 | 2.5kb | 2024-11-25 16:43:40 | 2024-11-25 16:44:07 |
Judging History
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%