QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#874255	#6140. 矩阵游戏	RDFZchenyy	50	2ms	10212kb	C++17	2.0kb	2025-01-27 21:28:57	2025-01-27 21:28:57

Judging History

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

[2025-01-27 21:28:57]
评测

测评结果：50
用时：2ms
内存：10212kb

查看

[2025-01-27 21:28:57]
提交

answer

#include<bits/stdc++.h>

using ll=long long;

#define MAXN 605
#define MAXM 100005

struct Edge{
    int v,nxt;
    ll w;
};

int n,m;
ll a[MAXN][MAXN];

Edge e[MAXM];
int h[MAXN],ec;
int qu[10000005],fr,bk;
int qcnt[MAXN],inq[MAXN];
ll dis[MAXN];

const ll mx=1000000;

void adde(int u,int v,ll w){
    e[ec].v=v,e[ec].w=w;
    e[ec].nxt=h[u]; h[u]=ec++;
    return;
}
void run(){
    std::cin>>n>>m;

    memset(a,0,sizeof(a));
    memset(h,-1,sizeof(h));
    memset(qcnt,0,sizeof(qcnt));
    memset(inq,0,sizeof(inq));
    memset(dis,0x3f,sizeof(dis));

    ec=0;
    for(int i=1;i<n;i++) for(int j=1;j<m;j++) std::cin>>a[i][j];
    for(int i=n-1;i>=1;i--){
        for(int j=m-1;j>=1;j--){
            a[i][j]-=(a[i+1][j]+a[i][j+1]+a[i+1][j+1]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(1&(i^j)){
                // +b_j-a_i
                adde(i,j+n,mx-a[i][j]);
                adde(j+n,i,a[i][j]);                
            }else{
                adde(j+n,i,mx-a[i][j]);
                adde(i,j+n,a[i][j]);
            }
        }
    }
    for(int i=1;i<=n+m;i++){
        adde(0,i,0);
    } 
    
    dis[0]=0;
    qu[fr=bk=1]=0;
    while(fr<=bk){
        int u=qu[fr++];
        inq[u]=0;
        qcnt[u]++;
        if(qcnt[u]>n+m) return (void)(std::cout<<"NO"<<'\n');
        for(int i=h[u];i+1;i=e[i].nxt){
            int v=e[i].v; ll w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                if(!inq[v]) qu[++bk]=v,inq[v]=1;
            }
        }
    }
    std::cout<<"YES"<<'\n';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            std::cout<<(a[i][j]+(((i^j)&1)?(-dis[i]):(dis[i]))+(((i^j)&1)?(dis[j+n]):(-dis[j+n])))<<" \n"[j==m];
        }     
    }
    return;
}

int T;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);

    memset(h,-1,sizeof(h));

    std::cin>>T;
    for(int i=1;i<=T;i++) run();

    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 5

Accepted

time: 2ms

memory: 8288kb

input:

output:

result:

ok you are right!!

Test #2:

score: 5

Accepted

time: 1ms

memory: 8548kb

input:

output:

result:

ok you are right!!

Test #3:

score: 5

Accepted

time: 1ms

memory: 8928kb

input:

output:

result:

ok you are right!!

Test #4:

score: 5

Accepted

time: 1ms

memory: 8296kb

input:

output:

result:

ok you are right!!

Test #5:

score: 5

Accepted

time: 0ms

memory: 10212kb

input:

output:

result:

ok you are right!!

Test #6:

score: 5

Accepted

time: 1ms

memory: 8544kb

input:

output:

result:

ok you are right!!

Test #7:

score: 5

Accepted

time: 2ms

memory: 9828kb

input:

output:

result:

ok you are right!!

Test #8:

score: 5

Accepted

time: 2ms

memory: 8292kb

input:

output:

NO
YES
647283 0
0 102846
747501 0
0 134576
781948 0
12310 200103
766133 0
0 184288
659865 0
0 16206
593438 0
0 0
421730 0
64977 200103
276696 0
466236 200103
318563 0
258336 200103
196118 0
466256 200103
239005 0
157825 200103
466265 0
251053 200103
131492 0
661375 200103
137602 0
257935 200103
4620...

result:

ok you are right!!

Test #9:

score: 5

Accepted

time: 2ms

memory: 8684kb

input:

output:

NO
YES
695456 0
0 298080
498364 0
0 500209
361888 0
0 433407
479661 0
0 497781
238111 0
184293 577595
170139 0
185227 577595
181915 0
145164 577595
184148 0
163618 577595
156111 0
262307 577595
110472 0
164547 577595
243932 0
0 498709
439158 0
0 244278
640848 0
0 234542
349106 0
72049 577595
79504 0...

result:

ok you are right!!

Test #10:

score: 5

Accepted

time: 0ms

memory: 9704kb

input:

output:

NO
YES
997572 0
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
33135 290221
319434 0
345445 290221
333253 0
0 202906
133199 0
317355 290221
229778 0
438306 290221
202508 0
166902 290221
399237 0
47579 290221
313915 0
244121 29...

result:

ok you are right!!

Test #11:

score: 0

Time Limit Exceeded

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:

result:

Test #12:

score: 0

Time Limit Exceeded

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:

result:

Test #13:

score: 0

Time Limit Exceeded

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:

result:

Test #14:

score: 0

Time Limit Exceeded

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:

result:

Test #15:

score: 0

Time Limit Exceeded

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:

result:

Test #16:

score: 0

Time Limit Exceeded

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
430810989324980 2313057 430823874612559 2380541 428259779118659 53640 428272663984176 -943000 430828169780221 4182621 430841053995994 2634152 428276959073351 -440185 428289843482343 -971241 430845349803188 3463268 430858234759602 2589345 428294139277998 67474 428307023640775 -474373 430862528...

result:

Test #17:

score: 0

Time Limit Exceeded

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
430810990418905 -334757 430823875120637 -1891718 428276959804230 -516525 428289844081592 -1255770 430828169897881 -742637 430841055264119 -1013015 428294139709485 -349871 428307024181499 -366747 430845349686808 -1130722 430858234453641 -1979891 428311319386460 -241605 428324204215898 -253674 ...

result:

Test #18:

score: 0

Time Limit Exceeded

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
428276956872142 1787417 428289842031211 1247763 430819578260083 1109397 430832463084547 1064816 428294136848769 947137 428307022015192 2007380 430836757435473 684055 430849642444059 1702980 428311316458215 1112396 428324202081246 2612463 430853937462645 414466 430866822563187 2441271 42832849...

result:

Test #19:

score: 0

Time Limit Exceeded

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
430810989445839 1993073 430823874841295 2669648 428276959200644 719873 428289844077064 2338512 430828169338984 1278383 430841054173742 2551697 428294138457668 1104559 428307023977920 2624937 430845349571463 807087 430858234230555 3364151 428311318983590 194823 428324203693064 1249232 43086252...

result:

Test #20:

score: 0

Time Limit Exceeded

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
430810989216427 1065355 430823874177919 1674547 428294139162106 636071 428307023465508 1525309 430828169704784 1992686 430841054004993 1343348 428311318989287 1545423 428324203465609 1417737 430845349346920 805301 430858234539548 2075431 428328498962158 -118389 428341383933056 1768151 4308625...