QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#373773	#5201. Cactus Meets Torus	InfinityNS	WA	1ms	6088kb	C++14	2.3kb	2024-04-02 05:22:17	2024-04-02 05:22:18

Judging History

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

[2024-04-02 05:22:18]
评测

测评结果：WA
用时：1ms
内存：6088kb

查看

[2024-04-02 05:22:17]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=100050;
vector<int> E[N];
void AddEdge(int u,int v){
	E[u].pb(v);
	E[v].pb(u);
}
int par[N];
bool was[N];
vector<int> cycLca;
vector<pair<int,int>> cyc;
int cnt[N];
int lid[N],rid[N],tid;
void DFS(int u,int p){
	par[u]=p;
	was[u]=true;
	lid[u]=++tid;
	for(int v:E[u]){
		if(v!=p){
			if(was[v]){
				if(lid[v]<lid[u]){
					cycLca.pb(v);
					cyc.pb({u,v});
					for(int i=u;i!=par[v];i=par[i]){
						cnt[i]++;
					}
				}
			}else{
				DFS(v,u);
			}
		}
	}
	rid[u]=tid;
}
int main(){
	while(true){
		int n,m;
		scanf("%i %i",&n,&m);
		if(n==0)break;
		for(int i=1;i<=m;i++){
			int sz;
			scanf("%i",&sz);
			vector<int> nodes(sz,0);
			for(int&j:nodes)scanf("%i",&j);
			for(int j=1;j<nodes.size();j++){
				AddEdge(nodes[j-1],nodes[j]);
			}
		}

		cycLca.clear();
		DFS(1,0);
		sort(cycLca.begin(),cycLca.end(),[&](int i,int j){return lid[i]<lid[j];});
		int lastCycNode=cycLca.size()?cycLca.back():0;
		for(int i=1;i<=n;i++){
			was[i]=false;
			par[i]=0;
			cnt[i]=0;
		}
		//printf("lastCycNode %i\n",lastCycNode);
		if(!lastCycNode){
			printf("Yes\n");
		}else{
			cycLca.clear();
			cyc.clear();
			DFS(lastCycNode,0);
			//printf("lastCycNode %i\n",lastCycNode);
			bool ok=true;
			sort(cycLca.begin(),cycLca.end(),[&](int i,int j){return lid[i]<lid[j];});
			int fir=cycLca.front();
			int las=cycLca.back();
			//for(int lca:cycLca)printf("cycLca %i (%i %i)\n",lca,lid[lca],rid[lca]);
			for(int i=1;i<cycLca.size();i++){
				//printf("cycLca %i\n",lca);
				if(rid[cycLca[i-1]]<lid[cycLca[i]]){
					ok=false;
				}
			}
			if(ok){
				ok=false;
				bool good=true;
				for(auto p:cyc){
					int deg=0,sec=0;
					for(int i=p.first;i!=par[p.second];i=par[i]){
						deg+=cnt[i]-1;
						if(cnt[i]>1)sec++;
					}
					if(deg==cyc.size()-1)ok=true;
					if(sec>2 || (sec>1 && cnt[par[p.second]]==0 && par[p.second]!=0))good=false;
					if(sec>1 && (p.second==fir || p.second==las))good=false;
				}
				if(ok || good)printf("Yes\n");
				else printf("No\n");
			}else{
				printf("No\n");
			}
		}

		for(int i=1;i<=n;i++){
			was[i]=false;
			par[i]=0;
			E[i].clear();
			cnt[i]=0;
		}
		tid=0;
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 6088kb

input:

6 1
8 1 2 3 1 4 5 6 4
10 2
9 1 2 3 1 10 4 5 6 4
5 7 8 9 7 10
0 0

output:

Yes
No

result:

ok 2 token(s): yes count is 1, no count is 1

Test #2:

score: -100

Wrong Answer

time: 1ms

memory: 6068kb

input:

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10
15 7
3 1 2 3
3 4 2 5
3 6 2 7
3 8 2 9
3 10 2 11
3 12 2 13
3 14 2 15
1 0
2 1
2 1 2
2 1
2 2 1
3 1
4 1 3 2 1
4 2
3 1 2 3
2 2 4
6 2
5 1 2 3 4 5
2 4 6
7 3
5 1 2 3 4 5
2 4 6
2 4 7
7 2
6 1 2 3 4 5 6
2 5 7
8 3
6 1 2 3 4 5 6
2 5 7
2 5 8
9 4
5 1 2 3 ...

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

wrong answer expected YES, found NO [1st token]