提供 SPJ
查看原帖
提供 SPJ
381463
McIron233楼主2024/11/20 19:24
#include "testlib.h"
#include<bits/stdc++.h>
const int N=4e5+3;
using namespace std;
int K,n;
set<set<int> >st; // edges
set<set<int> >st_v; // add_vertex
set<set<int> >covered; // covered
int fa[N];
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
struct addnode{ int a,b,c }arr[N];
struct tree{ int k,u[N],v[N]; }tree1,tree2;
signed main(int argc,char* argv[]){
	registerTestlibCmd(argc, argv);
	// * get info from standard input *
	n=inf.readInt();
	for(int i=0;i<=n-2;++i)
		st.insert({i,i+1});
	st.insert({0,n-1});
	for(int i=0;i<=n-4;++i){
		int u,v; cin>>u>>v;
		st.insert({u,v});
	}
	// * get info from standard input *
	// * get info from parti.'s answer *
	tree1.k=ouf.readInt(); tree1.k=ouf.readInt();
	for(int i=1;i<=tree1.k;++i){
		tree1.u[i]=ouf.readInt();
		tree1.v[i]=ouf.readInt();
	}
	tree2.k=ouf.readInt(); tree2.k=ouf.readInt();
	for(int i=1;i<=tree1.k;++i){
		tree2.u[i]=ouf.readInt();
		tree2.v[i]=ouf.readInt();
	}
	K=ouf.readInt();
	for(int i=1;i<=K;++i){
		arr[i].a=ouf.readInt();
		arr[i].b=ouf.readInt();
		arr[i].c=ouf.readInt();
	}
	// * get info from parti.'s answer *
	// * Judge K(>n or not) *
	if(K>n)quitf(_wa,"Too many vertexes added(>N).");
	// * Judge K(>n or not) *
	// * Attempt to add vertex(es) *
	for(int i=1;i<=K;++i){
		int a=arr[i].a;
		int b=arr[i].b;
		int c=arr[i].c;
		if(st.find({a,b})==st.end()
		or st.find({b,c})==st.end()
		or st.find({a,c})==st.end())
			quitf(_wa,"Some edges are missing when Jury is attempting to add a vertex.");
		if(st.find({a,b,c})!=st_v.end())
			quitf(_wa,"Repeated [a,b,c] when Jury is attempting to add a vertex.");
		st_v.insert({a,b,c});
		++n;
		st.insert({a,n});
		st.insert({b,n});
		st.insert({c,n});
	}
	// * Attempt to add vertex(es) *
	// * Attempt to cover vertex(es) using the trees parti. given *
	for(int i=0;i<n;++i)fa[i]=i;
	for(int i=0;i<tree1.k;++i){
		int u=find(tree1.u[i]);
		int v=find(tree1.v[i]);
		if(!(0<=tree1.u[i] && tree1.u[i]<n))
			quitf(_wa,"Improper vertex-id.");
		if(!(0<=tree1.v[i] && tree1.v[i]<n))
			quitf(_wa,"Improper vertex-id.");
		if(st.find({tree1.u[i],tree1.v[i]})==st.end())
			quitf(_wa,"Improper edge.");
		if(u==v)
			quitf(_wa,"The first graph parti. reported to Jury is not a tree.");
		fa[u]=v;
		covered.insert({tree1.u[i],tree1.v[i]});
	}
	for(int i=0;i<n;++i)fa[i]=i;
	for(int i=0;i<tree2.k;++i){
		int u=find(tree2.u[i]);
		int v=find(tree2.v[i]);
		if(!(0<=tree2.u[i] && tree2.u[i]<n))
			quitf(_wa,"Improper vertex-id.");
		if(!(0<=tree2.v[i] && tree2.v[i]<n))
			quitf(_wa,"Improper vertex-id.");
		if(st.find({tree2.u[i],tree2.v[i]})==st.end())
			quitf(_wa,"Improper edge.");
		if(u==v)
			quitf(_wa,"The second graph parti. reported to Jury is not a tree.");
		fa[u]=v;
		if(covered.find({tree2.u[i],tree2.v[i]})!=covered.end())
			quitf(_wa,"Two trees share edge(s).");
		covered.insert({tree2.u[i],tree2.v[i]});
	}
	if(tree1.k!=n-1)
		quitf(_wa,"The first tree parti. reported to Jury does not cover all vertexes.");
	if(tree2.k!=n-1)
		quitf(_wa,"The second tree parti. reported to Jury does not cover all vertexes.");
	// * Attempt to cover vertex(es) using the trees parti. given *
	// * Grant points *
	if(K==1)quitf(_ok,"Successfully constructed two trees and K is the least.");
	quitp(0.4,"Successfully constructed two trees but K is not the least.");
	// * Grant points *
}
2024/11/20 19:24
加载中...