QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#373799	#5208. Jumbled Trees	InfinityNS	RE	1ms	4040kb	C++20	6.8kb	2024-04-02 06:51:53	2024-04-02 06:51:53

Judging History

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

[2024-04-02 06:51:53]
评测

测评结果：RE
用时：1ms
内存：4040kb

查看

[2024-04-02 06:51:53]
提交

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]=2;

    vector<int>ret;
    int epe=dfs2(e[e1].a,-1,ret);
    ///if(!epe)while(1){}
    //printf("%d ADA\n",ret.size());
    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)while(1){}
    //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);

        /*for(int i=0;i<es.size();i++)printf("%d ",es[i]);
        printf(" CIKLUS\n");*/

        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<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);
            }
        }

        ///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);

        if(n==20 && m==30 && i>25){
            cout<<u<<" "<<v<<" "<<w<<endl;
        }

    }

    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;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3824kb

input:

output:

result:

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

Test #2:

score: 0

Accepted

time: 0ms

memory: 3792kb

input:

2 2 37
1 2 8
1 2 15

output:

result:

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

Test #3:

score: 0

Accepted

time: 0ms

memory: 3776kb

input:

output:

-1

result:

ok Both jury and participant did not find an answer

Test #4:

score: 0

Accepted

time: 1ms

memory: 4040kb

input:

output:

-1

result:

ok Both jury and participant did not find an answer

Test #5:

score: -100

Runtime Error

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: