QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373812#5208. Jumbled TreesInfinityNSTL 1ms4144kbC++207.9kb2024-04-02 07:38:182024-04-02 07:38:20

Judging History

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

  • [2024-04-02 07:38:20]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4144kb
  • [2024-04-02 07:38:18]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=1010;

struct edge{
    int a,b,w;
};
vector<edge>e;
vector<int>vect[maxn];
vector<pii>scand;
void add_edge(int a,int b,int w){
    vect[a].pb(e.size());
    vect[b].pb(e.size());
    e.pb({a,b,w});
}

int disc[maxn],mint[maxn],ctm;
int get_nxt(int eid,int x){
    if(e[eid].a==x)return e[eid].b;
    return e[eid].a;
}
int ecol[maxn],ncnt;
int compsum[maxn];
int pos[maxn];
int s;
int n,m;
void obradi(vector<int>edges){

    memset(pos,0,sizeof(pos));

    ncnt++;
    for(int i=0;i<edges.size();i++){
        int id=edges[i];

        //printf("%d ",id);

        pos[e[id].a]=1;
        pos[e[id].b]=1;

        ecol[id]=ncnt;
        compsum[ncnt]=add(compsum[ncnt],e[id].w);
    }
    //printf(" OB\n");
    int sz=-1;
    for(int i=1;i<=n;i++){
        sz+=pos[i];
    }

    scand.pb({compsum[ncnt],sz});

}
void find_bridges(int x,int p,vector<int>&stek){

    disc[x]=++ctm;
    mint[x]=disc[x];
    ///printf("%d %d XX\n",x,disc[x]);
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==p)continue;

        int nxt=get_nxt(vect[x][i],x);

        if(disc[nxt]<disc[x])stek.pb(id);

        if(disc[nxt])mint[x]=min(mint[x],disc[nxt]);
        else{
            find_bridges(nxt,id,stek);
            mint[x]=min(mint[x],mint[nxt]);

            if(mint[nxt]>=disc[x]){

                /*printf("%d %d %d EDGE\n",x,nxt,id);
                for(int i=0;i<stek.size();i++)printf("%d ",stek[i]);
                printf(" STEK\n");*/

                vector<int>edges;
                while(stek.back()!=id){
                    ///printf("%d sz\n",stek.size());
                    edges.pb(stek.back());
                    stek.pop_back();
                }
                edges.pb(stek.back());
                stek.pop_back();

                obradi(edges);

            }

        }

        //printf("%d %d | %d %d AAA\n",x,e[id].b,mint[e[id].b],disc[x]);
    }

///printf("%d RET\n",x);

}

bool calc_s(){

    int ep=0;
    s=0;
    for(int i=0;i<scand.size();i++){
        int v=scand[i].ff;
        int cc=scand[i].ss;

       // printf("%d %d \n",v,cc);

        if(cc==0){
            if(v!=0)return false;
        }
        else{
            int pom=mul(v,invv(cc));
            if(ep==0){
                ep=1;
                s=pom;
            }
            else{
                if(s!=pom)return false;
            }
        }

    }
    return true;
}

vector<pair<int,vector<int>>>ops;
void apply_mst(int v,vector<int>o){

    assert(o.size()==n-1);

    ops.pb({v,o});
    for(int i=0;i<o.size();i++){
        int id=o[i];
        e[id].w=sub(e[id].w,v);
        //printf("%d ",id);
    }
    /*printf(" | %d APPLIED\n",v);
    for(int i=0;i<e.size();i++){
        printf("%d ",e[i].w);
    }
    printf(" STATE\n");*/
}

void dfs(int x,int p,vector<int>&es){
    pos[x]=1;
    ///printf("%d dOSO\n",x);
    for(int i=0;i<vect[x].size();i++){
        int id=get_nxt(vect[x][i],x);
        if(pos[id])continue;
        es.pb(vect[x][i]);
        dfs(id,vect[x][i],es);
    }
}
void apply_rand_mst(){

    vector<int>edges;
    memset(pos,0,sizeof(pos));
    dfs(1,-1,edges);
    apply_mst(s,edges);

}

int dfs2(int x,int p,vector<int>&es){

    //printf("%d XX\n",x);

    if(pos[x]==2){
        pos[x]=1;
        return 1;
    }
    pos[x]=1;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        int v=get_nxt(vect[x][i],x);
        if(pos[v]==1)continue;
        if(pos[v]==2){
            es.pb(id);
            return 1;
        }

        if(dfs2(v,id,es)){
            es.pb(id);
            return 1;
        }

    }

    return 0;
}
vector<int>nadji_ciklus(int e1,int e2){

    memset(pos,0,sizeof(pos));
    pos[e[e2].a]=2;
    pos[e[e2].b]=1;
    pos[e[e1].b]=1;

    vector<int>ret;
    int epe=dfs2(e[e1].a,-1,ret);
    ///if(!epe)while(1){}
    if(!epe){
        vector<int>ret;
        return ret;
    }
    /*printf("%d ADA\n",ret.size());
    for(int i=0;i<ret.size();i++){
        int id=ret[i];
        printf("%d %d EDGE\n",e[id].a,e[id].b);
    }*/
    memset(pos,0,sizeof(pos));
    ///pos[e[e2].a]=2;
    pos[e[e2].b]=2;
    for(int i=0;i<ret.size();i++){
        pos[e[ret[i]].a]=pos[e[ret[i]].b]=1;
    }
    pos[e[e1].a]=1;
    epe=dfs2(e[e1].b,-1,ret);
    if(!epe){
        vector<int>ret;
        return ret;
    }
    /*if(!epe){

        printf("%d %d | %d %d %d %d LOS CIKLUS\n",e1,e2,e[e1].a,e[e1].b,e[e2].a,e[e2].b);
    }*/
    //printf("%d ADA\n",ret.size());

    ret.pb(e1);
    ret.pb(e2);
    return ret;

}
void solve_comp(int c){

    vector<int>cand;
    for(int i=0;i<e.size();i++){
        if(ecol[i]==c)cand.pb(i);
    }

    while(cand.size()){
        int id=cand.back();
        cand.pop_back();
        if(e[id].w==0)continue;
        int id2=cand.back();
        //printf("%d %d AA\n",id,id2);
        vector<int>es=nadji_ciklus(id,id2);
        if(es.size()==0){
            swap(e[id].a,e[id].b);
            es=nadji_ciklus(id,id2);
            if(es.size()==0){
                swap(e[id2].a,e[id2].b);
                es=nadji_ciklus(id,id2);
                if(es.size()==0){
                    swap(e[id].a,e[id].b);
                    es=nadji_ciklus(id,id2);
                }
            }
        }
        if(es.size()==0){
            printf("%d %d LOSEE\n",id,id2);
            while(1){}
        }

        /*for(int i=0;i<es.size();i++){
            int id=es[i];
            printf("%d %d |",e[id].a,e[id].b);
        }
        printf(" -> %d %d | %d %d  CIKLUS\n",e[id].a,e[id].b,e[id2].a,e[id2].b);*/

        memset(pos,0,sizeof(pos));
        for(int j=0;j<es.size();j++){
            int id=es[j];
            pos[e[id].b]=1;
            pos[e[id].a]=1;
        }

        vector<int>qry,qry2;
        for(int j=0;j<es.size();j++){
            int id=es[j];
            dfs(e[id].a,-1,qry);
            dfs(e[id].b,-1,qry);
        }

        qry2=qry;
        /*for(int j=0;j<qry.size();j++){
            int id=qry[j];
            printf("%d %d |",e[id].a,e[id].b);
        }
        printf(" TREE\n");*/

        for(int j=0;j<es.size();j++){
            int idc=es[j];
            if(idc==id)qry.pb(idc);
            else if(idc==id2)qry2.pb(idc);
            else{
                qry.pb(idc);
                qry2.pb(idc);
            }
        }
        ///printf("%d %d %d SIZES\n",qry.size(),qry2.size(),es.size());

        ///if(qry.size()!=n-1)while(1){}

        int goal=e[id].w;
        apply_mst(goal,qry);
        apply_mst(sub(0,goal),qry2);
    }

}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d %d %d",&n,&m,&mod);

    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        add_edge(u,v,w);

    }

    vector<int>stek;
    find_bridges(1,-1,stek);


    if(!calc_s()){
        printf("-1\n");
        return 0;
    }

    ///printf("%d SS\n",s);
    apply_rand_mst();

    for(int i=1;i<=ncnt;i++){
        solve_comp(i);
    }

    printf("%d\n",ops.size());
    for(int i=0;i<ops.size();i++){
        printf("%d ",ops[i].ff);
        vector<int>&pom=ops[i].ss;
        for(auto x:pom)printf("%d ",x+1);
        printf("\n");
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3796kb

input:

3 3 101
1 2 30
2 3 40
3 1 50

output:

5
60 1 2 
50 1 3 
51 1 2 
30 3 2 
71 3 1 

result:

ok Participant found an answer (5 trees) and jury found an answer (5 trees)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

2 2 37
1 2 8
1 2 15

output:

3
23 1 
15 2 
22 1 

result:

ok Participant found an answer (3 trees) and jury found an answer (3 trees)

Test #3:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

5 4 5
1 3 1
2 3 2
2 5 3
4 1 4

output:

-1

result:

ok Both jury and participant did not find an answer

Test #4:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

10 15 997
4 3 459
9 7 94
9 8 767
10 2 877
5 8 258
3 4 166
8 5 621
8 10 619
9 1 316
10 5 516
3 10 125
1 7 961
3 6 500
4 10 976
3 4 842

output:

-1

result:

ok Both jury and participant did not find an answer

Test #5:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

20 30 9973
1 10 696
3 8 2905
12 7 6609
20 10 1962
11 9 8430
19 2 412
6 3 6936
19 7 9113
14 15 5635
15 7 1770
13 10 3182
3 16 2625
17 1 7387
11 5 3700
9 15 1048
2 3 7717
12 10 8625
7 13 8141
5 14 2245
6 4 2819
18 19 8709
18 5 6191
17 10 7606
9 20 8626
17 4 8848
4 13 1073
10 8 2277
14 2 7714
11 8 5318...

output:

59
9375 1 4 24 5 14 19 9 10 3 8 6 16 2 7 20 25 26 12 21 
9860 5 15 9 28 6 8 3 17 1 13 25 20 26 4 21 14 2 12 30 
113 5 15 9 28 6 8 3 17 1 13 25 20 26 4 21 14 2 12 29 
5205 19 22 30 24 3 9 15 5 6 8 18 11 1 13 25 20 7 2 29 
4768 19 22 30 24 3 9 15 5 6 8 18 11 1 13 25 20 7 2 28 
2946 1 13 25 20 7 12 26 ...

result:

ok Participant found an answer (59 trees) and jury found an answer (59 trees)

Test #6:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

50 80 99991
6 5 67664
39 4 74944
11 9 13035
13 48 81979
40 20 57943
20 31 72081
1 6 39307
48 39 3550
28 48 41071
18 28 42935
37 32 7538
37 29 3815
50 37 88043
38 41 7283
40 26 66278
37 34 60696
47 19 80875
4 26 67
20 32 91858
39 24 83485
45 25 12241
48 46 61691
37 44 47541
39 40 70034
37 42 25006
27...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #7:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

100 150 999983
84 10 999545
69 48 930138
48 13 303468
36 6 668122
91 84 115623
62 71 59711
12 37 749281
86 49 281976
26 46 624831
91 8 450475
92 55 460900
50 63 513056
72 2 477622
26 96 11359
31 82 953946
6 71 406339
24 7 177090
70 4 67359
31 39 795565
47 32 407459
26 35 760698
22 37 508175
8 93 612...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #8:

score: 0
Accepted
time: 1ms
memory: 4056kb

input:

200 250 9999991
170 185 3242943
70 17 6083198
137 55 4000889
15 171 1113989
108 65 7988488
192 37 8812990
53 143 8707264
80 180 2504807
55 163 2706048
67 64 6210980
87 165 7693967
155 122 8550804
56 99 7228534
114 138 7047731
190 196 6684929
86 197 8866886
38 195 6717874
112 133 7257617
160 104 3210...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #9:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

500 600 99999989
265 416 47066772
354 266 16969437
195 415 7917612
354 136 43128175
163 191 58723996
144 84 65835385
157 45 94124747
232 441 17509499
70 397 64101208
223 387 7043647
320 47 84970673
100 2 87310855
87 131 75042257
101 391 27645446
79 26 68547739
390 185 92142961
257 15 80922292
276 48...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #10:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

500 700 99999989
250 2 71289880
454 447 70661327
328 253 57519343
11 201 67456781
294 99 23392419
215 322 61059212
411 389 69899684
488 429 89579827
437 79 60564061
413 380 34922641
477 372 14858185
156 44 3101349
88 8 52225146
115 26 8582010
171 237 33206748
237 495 31192017
146 32 62712576
209 352...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #11:

score: 0
Accepted
time: 1ms
memory: 4124kb

input:

500 800 99999989
258 304 1237432
159 152 6684056
8 47 64155938
436 265 83092505
204 302 3892712
142 302 77925167
37 15 20298972
202 395 35856655
284 260 96812598
365 172 48834835
196 101 64871741
174 45 37729972
302 206 90932677
305 275 27712443
443 157 81820535
16 248 22708463
461 479 64749118
105 ...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #12:

score: 0
Accepted
time: 1ms
memory: 4132kb

input:

500 900 99999989
122 188 44796717
73 121 56798468
334 358 95823235
485 453 96779071
209 391 45946094
332 168 91056077
481 483 81268636
148 393 25213027
107 214 99281713
493 46 61525618
472 355 74320568
258 482 99615552
159 393 20311839
411 121 5207095
20 131 65269699
45 339 51772607
195 292 64556504...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #13:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

500 1000 99999989
75 20 25003980
292 19 89418683
353 246 74910681
183 201 97535184
254 421 50614221
15 396 86624029
82 13 67776336
86 70 62843451
279 3 55801636
29 425 30024776
176 243 16631048
498 363 77415492
55 305 80862521
213 110 30693079
432 358 99667002
201 30 44433122
97 203 16284993
118 490...

output:

-1

result:

ok Both jury and participant did not find an answer

Test #14:

score: 0
Accepted
time: 1ms
memory: 4144kb

input:

500 499 999999937
287 228 350409600
392 107 350409600
458 22 350409600
362 425 350409600
368 136 350409600
364 71 350409600
211 265 350409600
167 116 350409600
195 353 350409600
489 477 350409600
380 85 350409600
281 15 350409600
263 247 350409600
453 122 350409600
104 187 350409600
331 223 35040960...

output:

1
350409600 214 267 66 113 137 376 28 30 432 370 389 364 42 399 117 272 241 35 285 232 329 483 227 244 11 419 333 47 24 171 83 306 258 61 324 19 298 231 216 280 464 249 439 206 134 336 383 43 158 86 179 436 470 135 192 475 366 388 265 72 348 368 458 484 401 130 136 235 450 52 3 199 417 266 477 166 4...

result:

ok Participant found an answer (1 trees) and jury found an answer (1 trees)

Test #15:

score: -100
Time Limit Exceeded

input:

500 510 999999937
417 280 770450784
207 303 770450784
472 396 770450784
345 191 964169440
164 67 770450784
492 302 770450784
5 71 770450784
386 22 770450784
77 25 487491058
430 467 770450784
148 95 770450784
288 215 770450784
55 451 10190666
215 69 770450784
267 195 770450784
487 283 770450784
435 3...

output:


result: