#P11414. [2025安徽省队集训]洞穴

[2025安徽省队集训]洞穴

题目背景

It is pitch black. You are likely to be eaten by a grue.

题面描述

你身处伸手不见五指的暗穴内。

在出发之前，你已经确定了暗穴的结构，暗穴可以看成 nn 个洞室相互连接的结构。

不幸的是，你不知道你在这 nn 个洞室中的哪一个。

对第 ii 个洞室，你知道可以进行 kik_i 种动作，其中第 jj 种操作由字符串 si,js_{i,j} 表示，并且你进行完这种动作之后会到达第 vi,jv_{i,j} 个洞室，而如果你进行了这 kik_i 种动作之外的动作，那么什么也不会发生。

你需要构造一种执行动作次数不超过 5×1055\times10^5 的序列，使得你无论初始在哪个洞室，最后都会到达并停在第 RR 个洞室，或者判断目标无法达成。

保证对于同一个 ii，si,js_{i,j} 互不相同，但是不保证 vi,jv_{i,j} 互不相同，并且也不保证 vi,j≠iv_{i,j}\neq i

输入格式

第一行一个正整数 nn，表示洞穴数量。

接下来 nn 行，每行第一个自然数表示 kik_i，接下来依次输入 $s_{i,1},v_{i,1},s_{i,2},v_{i,2},\cdots,s_{i,k_i},v_{i,k_i}$

最后一行一个正整数 RR，表示最后的终点

输出格式

如果无法达成目标，请在唯一的一行输出 No

如果可以达成目标，请输出三行：

第一行输出字符串 Yes

第二行输出你构造的序列长度 LL，请保证 0≤L≤5×1050\le L\le5\times10^5

第三行请输出 LL 个字符串，表示你依次执行的动作

输入输出样例

输入样例 #1

5
1 ne 2 
2 n 1 ne 3 
1 n 5 
1 n 2 
1 ne 1 
1

输出样例 #1

Yes
4
n n ne n

输入样例 #2

10
1 ns 3 
1 s 5 
2 s 4 e 1 
1 e 7 
1 e 4 
1 ns 4 
2 e 9 s 2 
1 e 10 
3 ns 7 e 10 s 1 
1 ns 7 
7

输出样例 #2

Yes
9
e s s ns s s e e ns

输入样例 #3

10
2 catch 9 narrow 9 
1 catch 6 
2 narrow 4 catch 7 
2 catch 3 narrow 7 
2 narrow 4 catch 2 
2 narrow 1 catch 3 
1 narrow 1 
1 narrow 10 
2 narrow 6 catch 8 
2 catch 9 narrow 3 
5

输出样例 #3

No

数据范围

Subtask1 (30pts)：1≤n≤101\le n\le10，保证 ∑ki≤100\sum k_i\le100

Subtask2 (10pts)：保证 si,j=nandeharuhikageyattanos_{i,j}=\texttt{nandeharuhikageyattano}

Subtask3 (60pts)：无特殊限制

对于所有数据，保证 1≤n≤100,1≤R,vi,j≤n1\le n\le100,1\le R,v_{i,j}\le n，且 si,js_{i,j} 均为长度不超过 3030 的小写字符串，保证 ∑ki≤9900\sum k_i\le9900

#include <bits/stdc++.h>
#define pii pair<int,int>
#define s1 first
#define s2 second
#define ID(i,j) (((i)-1)*n+(j))
#define prev o21923jore
using namespace std;
map<string,int> mp;
string imp[11111];
int to[111][11111];
int n;
vector<pii> G[111];
vector<pii> E[11111];
bool vis[11111];int dis[11111],prev[11111],prec[11111];
void bfs()
{
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;++i)q.push(ID(i,i)),vis[ID(i,i)]=1,dis[ID(i,i)]=0;
	while(!q.empty())
	{
		int p=q.front();q.pop();//printf("p:%d --- (%d,%d)\n",p,(p-1)/n+1,(p-1)%n+1);
		for(auto [v,c]:E[p])if(!vis[v])vis[v]=1,dis[v]=dis[p]+1,q.push(v),prec[v]=c,prev[v]=p;
	}
}
int R;
vector<pii> rG[111];
bool can[111];
int fa[111],faC[111];
void dfs(int u)
{
	can[u]=1;//printf("u:%d\n",u);
	for(auto [c,v]:rG[u])if(!can[v])dfs(v),fa[v]=u,faC[v]=c;
}
int main()
{
//	freopen("cave.in","r",stdin);freopen("cave.out","w",stdout);//setvbuf(stdout,0,_IONBF,0);
	scanf("%d",&n);int id=0;assert(1<=n&&n<=100);
	int sumk=0;
	for(int i=1;i<=n;++i)
	{
		int k;scanf("%d",&k);sumk+=k;
		vector<string> vs;
		for(int j=1;j<=k;++j)
		{
			string s;
			cin>>s;
			vs.push_back(s);
			int v;scanf("%d",&v);assert(1<=v&&v<=n);
			if(mp.find(s)==mp.end())mp[s]=++id,imp[id]=s;
			int ids=mp[s];
			to[i][ids]=v;
			G[i].push_back({ids,v});
			rG[v].push_back({ids,i});
		}
		for(int i=0;i+1<vs.size();++i)assert(vs[i]!=vs[i+1]);
	}
	assert(sumk<=9900);
	if(n<=10)assert(sumk<=100);
	scanf("%d",&R);assert(1<=R&&R<=n);
	for(int x=1;x<=n;++x)
	{
		for(int y=1;y<=n;++y)
		{
			for(auto [c,v]:G[x])E[ID(v,to[y][c]?to[y][c]:y)].push_back({ID(x,y),c});//,printf("x:%d c:%d v:%d to[%d][%d]:%d (%d,%d)<-(%d,%d)\n",x,c,v,y,c,v,v,to[y][c]?to[y][c]:y,x,y);
			for(auto [c,v]:G[y])E[ID(to[x][c]?to[x][c]:x,v)].push_back({ID(x,y),c});//,printf("(%d,%d)<-(%d,%d)\n",to[x][c]?to[x][c]:x,v,x,y);
		}
	}
	bfs();
	for(int x=1;x<=n;++x)for(int y=1;y<=n;++y)if(!vis[ID(x,y)]){printf("No\n");return 0;}//printf("passed first check\n");
	// printf("dis:");for(int i=1;i<=n*n;++i)printf("%d ",dis[i]);putchar(10);
	dfs(R);
	for(int i=1;i<=n;++i)if(!can[i]){printf("No\n");return 0;}
	vector<int> vv;
	for(int i=1;i<=n;++i)vv.push_back(i);
	vector<int> res;
	while(vv.size()>1)
	{
		int mn=1e9,I=-1,J=-1;
		for(int i=0;i<vv.size();++i)for(int j=i+1;j<vv.size();++j)if(dis[ID(vv[i],vv[j])]<mn){mn=dis[ID(vv[i],vv[j])];I=vv[i];J=vv[j];}
		// printf("I:%d J:%d\n",I,J);
		// printf("dis:\n");
		// for(int i=0;i<vv.size();++i)
		// {
		// 	for(int j=i+1;j<vv.size();++j)
		// 	{
		// 		printf("%d ",dis[ID(vv[i],vv[j])]);
		// 	}
		// 	putchar(10);
		// }
		int U=ID(I,J);
		int lst=res.size();
		while((U-1)%n+1!=(U-1)/n+1)
		{
			res.push_back(prec[U]);
			U=prev[U];
		}
		for(int &x:vv)
		{
			for(int i=lst;i<res.size();++i)
			{
				x=to[x][res[i]]?to[x][res[i]]:x;
			}
		}
		sort(vv.begin(),vv.end());
		vv.resize(unique(vv.begin(),vv.end())-vv.begin());
		// printf("vv:");for(int x:vv)printf("%d ",x);putchar(10);fflush(stdout);
	}
	int U=vv[1];
	while(U!=R)
	{
		res.push_back(faC[U]);U=fa[U];
	}
	printf("Yes\n%d\n",(int)res.size());
	for(int x:res)printf("%s ",imp[x].c_str());putchar(10);
//	fclose(stdin);fclose(stdout);
	return 0;
}

```cpp
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
FILE *fscore,*freport,*fstd,*fin,*fout;
int score=0;
map<string,int> mp;
int to[111][11111];
int main(int argc,char *argv[])
{
	registerTestlibCmd(argc,argv);
	fscore=fopen("score.log","w");
	freport=fopen("report.log","w");
	fstd=fopen(argv[2],"r");
	score=atoi(argv[1]);
	
	fin=fopen("user.in","r");
	fout=fopen("user.out","r");
	if (!fout)
	{
		fprintf(fscore,"%d",0);
		fprintf(freport,"No Output");
		fclose(fscore);
		fclose(freport);
		return 0;
	}
	
	int n;
	fscanf(fin, "%d", &n); 
	int id=0;
	for(int i=1;i<=n;++i)
	{
		int k;
		fscanf(fin, "%d", &k); 
		
		for(int j=1;j<=k;++j)
		{
			string s;
			s.resize(35);
			fscanf(fin, "%s", &s[0]); 
		
			int v;
			fscanf(fin, "%d", &v);
			if(mp.find(s)==mp.end())mp[s]=++id;
			int ids=mp[s];
			to[i][ids]=v;
		}
	}
	int R;
	fscanf(fin, "%d", &R);
	string sans,sout;
	sans.resize(35);
	sout.resize(35);
	fscanf(fstd, "%s", &sans[0]);
	fscanf(fout, "%s", &sout[0]);
//	=ans.readToken(),sout=ouf.readToken("Yes|No");
	if(sans!=sout)
	{
		fprintf(fscore,"%d",0);
		fprintf(freport,"Wrong");
	}
//	quitf(_wa,"Wrong yes/no\n");
	if(sans=="No")
	{
		fprintf(fscore,"%d",score);
		fprintf(freport,"Right");
	}
//	quitf(_ok,"Accepted\n");
	int L;
	fscanf(fout, "%d", &L);
//	=ouf.readInt(0,500000);
	static int c[111];
	for(int i=1;i<=n;++i)c[i]=i;
	for(int i=0;i<L;++i)
	{
		string s;
		s.resize(35);
		fscanf(fout, "%s", &s[0]);
//		=ouf.readToken("[a-z]{1,30}");
		int ids=mp[s];
		for(int _=1;_<=n;++_)c[_]=to[c[_]][ids]?to[c[_]][ids]:c[_];
	}
	for(int i=1;i<=n;++i)
		if(c[i]!=R)
		{
			fprintf(fscore,"%d",0);
			fprintf(freport,"Wrong");
		}
	fprintf(fscore,"%d",score);
	fprintf(freport,"Right");
	fclose(fscore);
	fclose(freport);
	fclose(fout);
	fclose(fstd);
	return 0;
//	quitf(_wa,"Node %d not at R\n",i);
//	quitf(_ok,"Accepted L:%d\n",L);
}
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  3. Worker 0, 36ms
  4. Powered by Hydro v4.19.1 Community