QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402017#5208. Jumbled TreesGraphcityRE 1ms3896kbC++202.6kb2024-04-29 19:12:172024-04-29 19:12:18

Judging History

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

  • [2024-04-29 19:12:18]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3896kb
  • [2024-04-29 19:12:17]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e3;

struct Node{int frm,to,nxt,id;} Edge[Maxn*2+5];
int tot,Head[Maxn+5],h[Maxn+5];
inline void Addedge(int x,int y,int id)
{
    Edge[++tot]=(Node){x,y,Head[x],id},Head[x]=tot;
    Edge[++tot]=(Node){y,x,Head[y],id},Head[y]=tot;
}

int n,m,Mod,X[Maxn+5],Y[Maxn+5],anc[Maxn+5],fat[Maxn+5],sum,cnt,all=-1;
int fa[Maxn+5],dep[Maxn+5],chk[Maxn+5],vis[Maxn+5],deg[Maxn+5];
vector<int> v[Maxn+5];
vector<pair<int,vector<int>>> ans;

inline int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%Mod;
        x=1ll*x*x%Mod,y>>=1;
    }
    return res;
}
inline void dfs(int x,int f)
{
    fat[x]=f,dep[x]=dep[f]+1;
    for(int i=Head[x];i;i=Edge[i].nxt)
    {
        int y=Edge[i].to; if(dep[y]) continue;
        fa[y]=Edge[i].id,chk[Edge[i].id]=1,dfs(y,x);
    }
}
inline void dfs1(int x)
{
    vis[x]=1,sum=(sum+h[x])%Mod,cnt=(cnt+1)%Mod;
    for(auto y:v[x]) if(!vis[y]) anc[y]=x,deg[x]++,dfs1(y);
}
inline void Work(int id)
{
    sum=0,cnt=Mod-1,dfs1(id);
    if(cnt==0 && sum!=0) {cout<<-1<<endl; exit(0);}
    if(cnt!=0)
    {
        int now=1ll*(Mod-sum)*Pow(cnt,Mod-2)%Mod;
        if(all!=-1 && all!=now) {cout<<-1<<endl; exit(0);} all=now;
    }
}

int main()
{
    // freopen("1.in","r",stdin);

    cin>>n>>m>>Mod;
    For(i,1,m)
    {
        int x,y; cin>>x>>y>>h[i]; X[i]=x,Y[i]=y;
        h[i]=(Mod-h[i])%Mod,Addedge(x,y,i);
    }
    dfs(1,0);
    For(i,1,m) if(!chk[i])
    {
        int x=X[i],y=Y[i]; if(dep[x]<dep[y]) swap(x,y);
        for(int j=x;j!=y;j=fat[j]) v[i].push_back(fa[j]),v[fa[j]].push_back(i);
    }
    For(i,1,m) if(!vis[i]) Work(i);
    if(all)
    {
        vector<int> w;
        For(i,1,m) if(chk[i]) w.push_back(i),h[i]=(h[i]+all)%Mod;
        ans.emplace_back(all,w);
    }
    queue<int> q; For(i,1,m) if(!deg[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front(),y=anc[x]; q.pop();
        if(!y) assert(!h[x]);
        if(h[x])
        {
            vector<int> w1,w2;
            int k=(Mod-h[x])%Mod; h[x]=(h[x]+k)%Mod,h[y]=(h[y]-k+Mod)%Mod;
            For(i,1,m) if(i!=x && (chk[i] || i==y)) w2.push_back(i);
            For(i,1,m) if(i!=y && (chk[i] || i==x)) w1.push_back(i);
            ans.emplace_back(k,w1),ans.emplace_back((Mod-k)%Mod,w2);
        } if(y && --deg[y]==0) q.push(y);
    }
    cout<<ans.size()<<endl;
    for(auto [k,w]:ans) {cout<<k<<' '; for(auto i:w) cout<<i<<' '; cout<<endl;}
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3592kb

input:

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

output:

5
60 2 3 
81 2 3 
20 1 3 
91 2 3 
10 1 2 

result:

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

Test #2:

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

input:

2 2 37
1 2 8
1 2 15

output:

3
23 2 
29 2 
8 1 

result:

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

Test #3:

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

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: 3896kb

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: -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:


result: