QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#697449#8333. GiftKOH-#WA 1ms5740kbC++142.1kb2024-11-01 14:08:292024-11-01 14:08:29

Judging History

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

  • [2024-11-01 14:08:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5740kb
  • [2024-11-01 14:08:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch))	f|=ch=='-',ch=getchar();
	while(isdigit(ch))	x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;return;
} 
template <typename T>
inline void print(T x){
	if(x<0)	putchar('-'),x=-x;
	if(x>9)	print(x/10);
	putchar(x%10^48);return; 
}

#define ll long long 
const int N=1e5+3;
int head[N],to[N<<1],Next[N<<1],tot;
void Addedge(int u,int v){
	to[++tot]=v,Next[tot]=head[u],head[u]=tot;
	return;
} 
int in[N],id[N],n;
bool Cmp(int x,int y){
	return in[x]>in[y];
}
int fa[N],dep[N],cnt;
bool ring[N];
void Dfs(int u,int f){
	dep[u]=dep[f]+1,fa[u]=f;
//	cout<<u<<" "<<dep[u]<<"???\n"; 
	for(int i=head[u];i;i=Next[i]){
	
		int v=to[i];
		
//		cout<<u<<" "<<v<<"??\n";
		if(v==f)	continue;
		if(dep[v]<dep[u]&&dep[v]){
			int now=u;ring[u]=true;
			while(now!=v&&now){
				now=fa[now];
				ring[now]=true;
//				cout<<now<<"???\n";
			}
			cnt=dep[v]-dep[u]+1;
		}
		else Dfs(v,u);
	
	}
}
int main(){
//	int T;read(T);
//	while(T--){
		read(n);
		for(int i=1;i<=n;++i){
			id[i]=i;int u,v;read(u),read(v);
			Addedge(u,v),Addedge(v,u);
			in[u]++,in[v]++;
		}
		id[n]=n;
		sort(id+1,id+n+1,Cmp);
		Dfs(1,0);
		if(in[id[1]]>5){
			puts("0");
		}
		else if(in[id[n]]==0){
			puts("0");
		}
		else{
			if(in[id[3]]==5) puts("0");
			else if(in[id[1]]!=5){
				print(1ll*(n-1)*cnt),putchar('\n');
			}
			else{
				if(in[id[2]]==5){
					if(ring[id[1]]&&ring[id[2]]) print(n-1),putchar('\n');
					else puts("0");
				}
				else{
					if(ring[id[1]]){
						int res=0;
						for(int i=head[id[1]];i;i=Next[i]){
//							int y=to[i];cout<<y<<"??\n"
							if(ring[to[i]])	res++; 
						} 
						
						print(1ll*(n-1)*res),putchar('\n');
					}
					else puts("0");
				}
			}
		}
//		for(int i=1;i<=n;++i)	id[i]=head[i]=fa[i]=dep[i]=in[i]=0,ring[i]=false;
//		for(int i=1;i<=tot;++i)	to[i]=Next[i]=0;
//		tot=0;
//	}
	
	return 0;
}
/*
5
1 2
2 4
4 3
1 3
1 4
*/
	

详细

Test #1:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 5740kb

input:

3
1 3
3 2
2 1

output:

-2

result:

wrong answer 1st numbers differ - expected: '9', found: '-2'