QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72896#5208. Jumbled TreesskiceanWA 2ms3792kbC++143.4kb2023-01-19 22:40:522023-01-19 22:40:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-19 22:40:53]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3792kb
  • [2023-01-19 22:40:52]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <vector>
#include <cassert>
#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;
			assert(((ji.se-1)*ztad%P+ji.fi)%P==0);
			break;
		}
	}
	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){
		// if(N==20&&M==30&&P==9973)printf("-1 ***\n"),printf("%d %lld\n",ztad,(LL)ksm((N-1)%P,P-2)*sum%P);
		/*else */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: 2ms
memory: 3632kb

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: 2ms
memory: 3720kb

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

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

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

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)