QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#484309 | #6140. 矩阵游戏 | weiguoliang | 100 ✓ | 248ms | 9352kb | C++14 | 2.1kb | 2024-07-19 17:25:27 | 2024-07-19 17:25:28 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 305
using namespace std;
struct node{
ll t,n,w;
}edge[N*N<<1];
ll a[N][N],b[N][N],dis[N<<1],head[N<<1],cn=-1,cnt[N<<1],n,m;
bool vis[N<<1],p;
queue<ll>q;
ll read(){char c=getchar();
ll n=0;
while(c<'0'||c>'9')c=getchar();
while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=getchar();
return n;
}
void add(ll a,ll b,ll c){
edge[++cn]={b,head[a],c};
head[a]=cn;
}
int main(){ll i,k,t,f;
t=read();
while(t--){n=read(),m=read(),p=true;
memset(head,-1,sizeof(head)),cn=-1;
for(i=1;i<n;i++)for(k=1;k<m;k++)b[i][k]=read();
for(i=2;i<=n;i++){
for(k=2;k<=m;k++){
a[i][k]=b[i-1][k-1]-a[i-1][k-1]-a[i-1][k]-a[i][k-1];
}
}
for(i=1;i<=n;i++){
for(k=1;k<=m;k++){
if((i&1)==(k&1)){
add(i,k+n,a[i][k]);
add(k+n,i,1e6-a[i][k]);
}
else{
add(i,k+n,1e6-a[i][k]);
add(k+n,i,a[i][k]);
}
}
}
memset(dis,0x3f,sizeof(dis)),memset(cnt,0,sizeof(cnt));
dis[1]=0;
q.push(1),vis[1]=true;
while(!q.empty()&&p){f=q.front(),q.pop(),vis[f]=false;
for(i=head[f];i!=-1;i=edge[i].n){
if(dis[edge[i].t]>dis[f]+edge[i].w){
dis[edge[i].t]=dis[f]+edge[i].w,cnt[edge[i].t]++;
if(cnt[edge[i].t]>n+m){
p=false;
break;
}
if(!vis[edge[i].t])q.push(edge[i].t),vis[edge[i].t]=true;
}
}
}
if(!p){
cout<<"NO\n";
continue;
}
cout<<"YES\n";
for(i=1;i<=n;i++){
for(k=1;k<=m;k++){
if((i&1)==(k&1))a[i][k]+=dis[i]-dis[k+n];
else a[i][k]+=dis[k+n]-dis[i];
cout<<a[i][k]<<' ';
}
cout<<'\n';
}
}
}
詳細信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 3480kb
input:
10 3 3 9 21 22 16 3 3 28 30 13 4 3 3 17 10 5 30 3 3 30 27 30 25 3 3 22 19 28 12 3 3 30 27 21 28 3 3 4 25 11 5 3 3 12 24 24 30 3 3 5 4 27 8 3 3 20 29 17 18
output:
YES 0 9 0 0 0 12 22 0 4 YES 0 28 0 0 0 2 13 0 2 YES 2 10 0 5 0 0 0 0 30 YES 0 27 0 3 0 0 27 0 25 YES 0 19 0 3 0 0 25 0 12 YES 0 27 0 3 0 0 18 0 28 YES 0 4 16 0 0 5 11 0 0 YES 0 12 0 0 0 12 24 0 18 YES 0 4 0 1 0 0 26 0 8 YES 0 20 0 0 0 9 17 0 9
result:
ok you are right!!
Test #2:
score: 5
Accepted
time: 1ms
memory: 5768kb
input:
10 3 3 5 18 16 21 3 3 28 30 27 5 3 3 30 12 9 11 3 3 28 20 30 13 3 3 22 27 28 5 3 3 30 29 30 23 3 3 17 13 22 13 3 3 29 24 29 25 3 3 23 12 3 2 3 3 20 30 23 30
output:
YES 0 5 0 0 0 13 16 0 8 YES 0 28 0 0 0 2 27 0 3 YES 9 12 0 9 0 0 0 0 11 YES 0 20 0 8 0 0 22 0 13 YES 0 22 0 0 0 5 28 0 0 YES 0 29 0 1 0 0 29 0 23 YES 0 13 0 4 0 0 18 0 13 YES 0 24 0 5 0 0 24 0 25 YES 8 12 0 3 0 0 0 0 2 YES 0 20 0 0 0 10 23 0 20
result:
ok you are right!!
Test #3:
score: 5
Accepted
time: 0ms
memory: 3612kb
input:
10 3 3 17 22 17 27 3 3 30 24 30 30 3 3 11 16 10 15 3 3 29 18 19 27 3 3 12 2 25 26 3 3 27 28 29 30 3 3 14 11 8 16 3 3 29 27 26 15 3 3 1 21 25 12 3 3 30 28 21 27
output:
YES 0 17 0 0 0 5 17 0 22 YES 0 24 0 6 0 0 24 0 30 YES 0 11 0 0 0 5 10 0 10 YES 0 18 0 11 0 0 8 0 27 YES 0 2 0 10 0 0 15 0 26 YES 0 27 0 0 0 1 29 0 29 YES 0 11 0 3 0 0 5 0 16 YES 0 27 0 2 0 0 24 0 15 YES 0 1 8 0 0 12 25 0 0 YES 0 28 0 2 0 0 19 0 27
result:
ok you are right!!
Test #4:
score: 5
Accepted
time: 0ms
memory: 3596kb
input:
10 3 3 6 30 30 11 3 3 29 28 11 25 3 3 26 26 15 22 3 3 23 30 29 6 3 3 16 8 13 20 3 3 26 30 29 28 3 3 3 24 4 2 3 3 29 30 24 29 3 3 15 12 7 4 3 3 30 26 25 30
output:
YES 0 6 13 0 0 11 30 0 0 YES 0 28 0 1 0 0 10 0 25 YES 0 26 0 0 0 0 15 0 22 YES 0 23 1 0 0 6 29 0 0 YES 0 8 0 8 0 0 5 0 20 YES 0 26 0 0 0 4 29 0 24 YES 0 3 19 0 0 2 4 0 0 YES 0 29 0 0 0 1 24 0 28 YES 0 12 0 3 0 0 4 0 4 YES 0 26 0 4 0 0 21 0 30
result:
ok you are right!!
Test #5:
score: 5
Accepted
time: 0ms
memory: 3508kb
input:
10 10 2 240 8788 3257 6676 9748 4941 1268 2569 7827 10 2 9542 9328 8351 9362 9771 9183 8527 8640 7370 10 2 3144 7704 2054 9901 3567 120 2273 2407 4202 10 2 7337 9013 9119 9547 8526 8071 8475 6682 9273 10 2 746 9791 1891 3204 8908 1495 1353 9406 1176 10 2 9884 6039 4691 9956 8516 9454 9649 8966 9380 ...
output:
NO YES 0 7048 0 2494 6834 0 0 1517 7845 0 0 1926 7257 0 0 1270 7370 0 0 0 NO YES 0 6422 0 915 8098 0 0 1021 8526 0 0 0 8071 0 0 404 6278 0 0 2995 NO YES 0 7096 0 2788 3251 0 0 1440 8516 0 0 0 9454 0 0 195 8771 0 0 609 NO YES 0 8958 0 0 8441 0 0 1184 7886 0 0 1159 ...
result:
ok you are right!!
Test #6:
score: 5
Accepted
time: 1ms
memory: 5672kb
input:
10 10 2 7221 6762 7271 4154 1804 3226 6434 8357 2359 10 2 8581 5933 9174 9731 9716 9180 8744 9947 6264 10 2 282 9689 7228 960 2522 6806 7516 7002 9829 10 2 9202 8816 8250 9267 8287 8105 9707 8985 9226 10 2 2004 254 7197 7613 9790 5556 3064 6363 6489 10 2 7863 9827 9600 9998 7626 6038 9530 8772 8501 ...
output:
NO YES 0 7688 0 893 5040 0 0 4134 5597 0 0 4119 5061 0 0 3683 6264 0 0 0 NO YES 0 7656 0 1546 7270 0 0 980 8287 0 0 0 8105 0 0 1602 7383 0 0 1843 NO YES 0 5264 0 2599 7228 0 0 2372 7626 0 0 0 6038 0 0 3492 5280 0 0 3221 NO YES 0 6291 0 1856 7172 0 0 0 9481 0 0 283 ...
result:
ok you are right!!
Test #7:
score: 5
Accepted
time: 1ms
memory: 5664kb
input:
10 10 2 2492 6642 8650 4949 7971 7552 5729 6137 3224 10 2 8862 4232 4370 9422 9787 8443 9745 9230 9708 10 2 1073 3311 5736 6108 1985 2880 2596 1260 4678 10 2 9862 9822 8867 4686 9645 7259 7954 9855 9482 10 2 6532 3248 1799 3767 7693 4389 5786 1124 9586 10 2 7667 9393 6828 8642 9482 8512 8366 7067 87...
output:
YES 0 2492 0 0 6642 0 0 2008 2941 0 0 5030 2522 0 0 3207 2930 0 0 294 YES 0 8862 0 0 4232 0 0 138 9284 0 0 503 7940 0 0 1805 7425 0 0 2283 NO YES 0 8907 0 955 8867 0 0 0 4686 0 0 4959 2300 0 0 5654 4201 0 0 5281 NO YES 0 5102 0 2565 6828 0 0 0 8642 0 0 840 7672 0 ...
result:
ok you are right!!
Test #8:
score: 5
Accepted
time: 1ms
memory: 3940kb
input:
10 100 2 407406 741582 966880 693984 175204 991130 183615 326373 131306 366816 697972 180227 398068 835836 746523 999640 178807 545159 437329 536071 721606 306737 181599 455551 733444 231865 77996 588988 897019 804401 528918 524503 349494 623245 534144 344637 25518 791164 100668 547254 630911 346372...
output:
NO YES 0 647283 0 102846 747501 0 0 134576 781948 0 0 212413 766133 0 0 184288 659865 0 0 16206 593438 0 0 0 421730 0 0 265080 276696 0 0 666339 318563 0 0 458439 196118 0 0 666359 239005 0 0 357928 466265 0 0 451156 131492 0 0 861478 137602 0 0 458038 462088 0 0 399664 ...
result:
ok you are right!!
Test #9:
score: 5
Accepted
time: 1ms
memory: 6032kb
input:
10 100 2 514849 121431 445450 996530 912655 547635 39581 89505 975458 843069 273144 700881 59053 289340 848708 32178 700710 194859 273472 213196 384827 341987 482545 308239 413944 599935 848280 843825 979288 195213 209986 440149 934390 768000 882462 200861 119570 174661 871708 511415 426500 576587 5...
output:
NO YES 0 695456 0 298080 498364 0 0 500209 361888 0 0 433407 479661 0 0 497781 238111 0 0 761888 170139 0 0 762822 181915 0 0 722759 184148 0 0 741213 156111 0 0 839902 110472 0 0 742142 243932 0 0 498709 439158 0 0 244278 640848 0 0 234542 349106 0 0 649644 79504 0 0 53...
result:
ok you are right!!
Test #10:
score: 5
Accepted
time: 1ms
memory: 4024kb
input:
10 100 2 650385 567657 465159 181316 696069 211308 655715 128129 988551 838473 44280 61031 528962 277047 286263 142130 248066 307713 578918 695526 89569 48119 569157 673222 295474 923221 90394 912892 523136 369133 635906 272262 887296 438346 625250 217263 729637 256075 898161 999382 845113 626531 74...
output:
NO YES 0 997572 0 0 831313 0 0 140282 842484 0 0 130157 481725 0 0 160423 809914 0 0 126258 313950 0 0 227108 721150 0 0 198312 629558 0 0 323356 319434 0 0 635666 333253 0 0 202906 133199 0 0 607576 229778 0 0 728527 202508 0 0 457123 399237 0 0 337800 313915 0 0 534342...
result:
ok you are right!!
Test #11:
score: 5
Accepted
time: 188ms
memory: 9104kb
input:
10 300 298 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0...
output:
NO YES 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0...
result:
ok you are right!!
Test #12:
score: 5
Accepted
time: 248ms
memory: 9012kb
input:
10 297 296 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0...
output:
NO YES 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0...
result:
ok you are right!!
Test #13:
score: 5
Accepted
time: 226ms
memory: 9148kb
input:
10 297 299 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1...
output:
NO YES 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0...
result:
ok you are right!!
Test #14:
score: 5
Accepted
time: 227ms
memory: 9200kb
input:
10 298 299 0 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0...
output:
NO YES 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0...
result:
ok you are right!!
Test #15:
score: 5
Accepted
time: 181ms
memory: 9352kb
input:
10 298 296 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1...
output:
NO YES 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0...
result:
ok you are right!!
Test #16:
score: 5
Accepted
time: 156ms
memory: 9028kb
input:
10 295 299 3600561 469227 1519243 508870 2714139 2548515 3416122 1633507 1829918 1551817 3098121 1670950 2106466 1946727 1581396 3426393 1988045 2888135 2146489 1534631 2721599 3729764 456043 293501 882439 3099151 2941143 3610816 549774 1066237 3189705 2413286 2316602 3976215 3845403 862960 241887 2...
output:
NO YES 40962 374702 893605 381010 178958 309380 702311 776779 962531 532460 54742 456279 285839 297601 0 332823 668671 597676 639677 201156 755284 341963 804343 986488 696859 577845 313308 368833 440471 33175 46188 838454 653397 248867 861602 926513 670150 275280 551854 232003 646893 474400 856302 9...
result:
ok you are right!!
Test #17:
score: 5
Accepted
time: 137ms
memory: 9132kb
input:
10 298 297 1203979 2459461 1123626 2165742 593951 2361185 60882 1597698 966249 1407808 2665213 1585110 1730464 732707 2642476 54357 96750 3459440 500455 1509802 2084769 1885656 824649 1394960 3065480 1964072 626742 582644 617926 652074 1646286 250370 1154127 1955950 327344 753408 2005921 2832519 933...
output:
NO YES 474964 964355 163344 90207 358090 597313 412221 608943 504816 306797 122022 596450 541718 75006 689372 678731 954578 763437 300893 329087 285525 677800 203131 456530 198144 473968 211932 69940 494211 422697 851734 382528 812941 793472 769781 294957 0 797356 118136 521348 699433 1000000 208993...
result:
ok you are right!!
Test #18:
score: 5
Accepted
time: 162ms
memory: 9116kb
input:
10 296 296 2917992 3146628 3606537 755096 2325656 3902232 2435726 2851482 3134088 1183312 3680091 2970485 3974463 2456731 3306154 400789 1137399 1266637 1849976 2126197 1039996 2867787 711979 2828033 1651264 3781772 1152035 2861694 2479767 1853717 886722 2972156 4583 903432 3364054 3947134 3871761 3...
output:
NO YES 894268 366446 501458 260696 0 881413 534711 131475 474460 737885 666625 731028 501057 445669 188780 440964 109620 397608 257042 394292 685186 568279 77742 371609 898607 815500 360564 133369 502810 255584 272961 608235 144856 34640 495346 121587 819423 214427 886379 220149 810661 984090 63547 ...
result:
ok you are right!!
Test #19:
score: 5
Accepted
time: 152ms
memory: 9148kb
input:
10 297 297 13391 712464 2974864 1439202 1447544 1413180 800048 597109 3349875 2034207 1467293 796338 2354278 171222 1066675 2532591 208592 123178 2912280 3309432 3409173 1029236 2315777 2135394 3355241 69077 3113692 2937527 2948148 1151724 1640840 870814 42569 2304251 726055 3017332 2049772 2646010 ...
output:
NO YES 295400 213122 463211 820546 760413 848420 743800 34587 770632 874409 65184 749261 165625 739971 236954 201458 941789 978089 282983 94942 857768 305286 477846 118895 624491 364471 0 465403 865310 364928 921272 346270 312588 755027 0 480181 525908 373944 92637 681381 786361 827765 492049 205550...
result:
ok you are right!!
Test #20:
score: 5
Accepted
time: 149ms
memory: 9264kb
input:
10 297 295 2251173 2102586 854138 210476 3746962 1050335 357886 1246625 2048656 3914401 2622120 2500826 3210040 3638713 646704 3538951 2675262 2202513 1600647 2451535 120429 782584 3574033 3344068 580591 2179489 3256587 684504 1805546 599720 3155847 2286982 2960267 502472 3365334 1420188 2393737 228...
output:
NO YES 296724 862096 358748 615336 134239 845418 955015 19394 510782 988068 899764 594941 559023 814572 326733 246873 457545 788542 455140 129283 814735 598716 130562 1000000 699252 1000000 769428 378357 373590 788233 629196 660745 449732 570461 242856 31474 594270 139739 354395 371485 318967 723288...
result:
ok you are right!!
Extra Test:
score: 0
Extra Test Passed