QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#72890 | #5208. Jumbled Trees | skicean | WA | 2ms | 3820kb | C++14 | 3.3kb | 2023-01-19 22:16:36 | 2023-01-19 22:16:39 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <vector>
#define macro_expand(x) #x
#define print_macro(x) printf("%s\n",macro_expand(x))
#define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i)
#define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i)
#define go(p,u) for(int p=head[u];p;p=edge[p].nxt)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
const int MN=505,MM=1005;
int N,M,P;
int add(int &x,const int &y){return ((x+=y)>=P)?(x-=P):x;}
int head[MN];
struct E{
int v,nxt,id;
E():v(0),nxt(0),id(0){}
E(int _v,int _nxt,int _id):v(_v),nxt(_nxt),id(_id){}
}edge[MM*2];
int tote;
void AddE(int u,int v,int id){
edge[++tote]=E(v,head[u],id);
head[u]=tote;
}
int val[MM],fa[MN],fid[MN];
bool tre[MM],vis[MN],evis[MM];
vector<int> G[MM];
int dep[MN];
void dfs1(int u){
vis[u]=1;
go(p,u){
int v=edge[p].v,id=edge[p].id;
if(!vis[v]){
dep[v]=dep[u]+1;
fa[v]=u,fid[v]=id,tre[id]=1;
evis[id]=1;
dfs1(v);
}else if(!evis[id]){ // 这个地方必须看这条边是不是被访问过了
evis[id]=1;
int now=u;
while(now!=v){
G[id].push_back(fid[now]);
G[fid[now]].push_back(id);
now=fa[now];
}
}
}
}
struct Node{
int u,v,w;
Node():u(0),v(0),w(0){}
Node(int _u,int _v,int _w):u(_u),v(_v),w(_w){}
};
vector<Node> ans;
bool ee[MM]; // 不能用 vis 了
void dfs2(int u){
ee[u]=1;
for(int v:G[u]){
if(!ee[v]){
dfs2(v);
ans.push_back(Node(v,u,val[v]));
add(val[u],val[v]); // 开始这个地方忘了加了
val[v]=0;
}
}
}
void print(int i1,int i2,int v){
if(v==0)return;
bool tag=0;
if(tre[i1])printf("%d ",P-v),tag=1;
else printf("%d ",v),tag=0;
FOR(i,1,M)if(tre[i])printf("%d ",i);
printf("\n");
if(tag)printf("%d ",v);
else printf("%d ",P-v);
if(!tre[i1])printf("%d ",i1);
else printf("%d ",i2);
FOR(i,1,M)if(i!=i1&&i!=i2&&tre[i])printf("%d ",i);
printf("\n");
}
int ksm(int x,int y){
int ret=1;
for(;y;y>>=1,x=(LL)x*x%P)if(y&1)ret=(LL)ret*x%P;
return ret;
}
int gsum;
bool gv[MM];
pii get_sum(int u){
gv[u]=1;
int ret=val[u],c=1;
for(int v:G[u])if(!gv[v]){
auto yi=get_sum(v);
add(ret,yi.fi),c+=yi.se;
}
return mp(ret,c);
}
int main(){
// freopen("j.in","r",stdin);
// freopen("j.out","w",stdout);
scanf("%d%d%d",&N,&M,&P);
int sum=0;
FOR(i,1,M){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(sum,w);
AddE(u,v,i),AddE(v,u,i);
if(w)val[i]=P-w;
else val[i]=0;
}
int ztad=0;
// if((N-1)%P==0){
// if(sum%P!=0){
// printf("-1\n");
// return 0;
// }
// ztad=0;
// }else
// ztad=(LL)ksm((N-1)%P,P-2)*sum%P;
dfs1(1);
FOR(i,1,M)if(!gv[i]){
auto ji=get_sum(i);
if((ji.se-1)%P==0&&ji.fi%P!=0){
printf("-1\n");
return 0;
}else if(ji.fi%P!=0)
ztad=(LL)ksm((ji.se-1)%P,P-2)*(P-ji.fi)%P;
}
FOR(i,1,M)if(tre[i])add(val[i],ztad);
FOR(i,1,M)if(!ee[i])dfs2(i);
FOR(i,1,M)if(val[i]!=0){
printf("-1\n");
return 0;
}
int ttt=0;
for(auto v:ans)ttt+=(v.w!=0);
printf("%d\n",ttt*2+(ztad!=0));
if(ztad){
printf("%d ",ztad);
FOR(i,1,M)if(tre[i])printf("%d ",i);
printf("\n");
}
for(auto ko:ans)print(ko.u,ko.v,ko.w);
// fclose(stdin);
// fclose(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3688kb
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: 2ms
memory: 3784kb
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: 2ms
memory: 3820kb
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
Wrong Answer
time: 2ms
memory: 3656kb
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:
-1
result:
wrong answer Participant did not find an answer, while jury found (59 trees)