代码求调
  • 板块P11017 Hide And Seek
  • 楼主1nes
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/22 10:45
  • 上次更新2024/11/22 14:32:35
查看原帖
代码求调
1114867
1nes楼主2024/11/22 10:45

使用同一个队列判断距离的想法是正确的吗

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
using namespace std;
#define ra	read()
#define gc	getchar()
#define el	puts("")
#define lowbit(x)	x & -x
#define ls	p << 1
#define rs	p << 1 | 1
inline int read(){
	int x = 0 , f = 1;
	char ch = gc;
	while(ch > '9' || ch < '0'){
		if(ch == '-')	f = -1;
		ch = gc;
	}
	while(ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = gc;
	}
	return x * f;
}
void write(int x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9){
		write(x / 10);
	}
	putchar(x % 10 + 48);
}
void w1(int x){
	write(x);
	el;
}
void w2(int x){
	write(x);
	putchar(' ');
}
void w(int x){
	write(x);
}
const int N = 2e5 + 3;
const int mod = 998244353;
const int inf = 1e9 + 7;

int T , n , p , q;
int du[N];
int vis[N];
struct node{
	int x , id;
};
struct edge{
	int u , v;
};
vector<edge>	ve[N];
void init(){
	n = ra , p = ra , q = ra;
	for(int i = 1 ; i <= n ; i++){
		ve[i].clear();
		du[i] = 0;
	}
	for(int i = 1 ; i <= n - 1 ; i++){
		int x = ra , y = ra;
		ve[x].push_back({x , y});
		ve[y].push_back({y , x});
		du[x]++;
		du[y]++;
	}
}
int frz;
void solve(){
	bool flag = 0;
	queue<node> qu;
	qu.push({p , 0});
	while(!qu.empty()){
		int u = qu.front().x , io = qu.front().id;
		if(frz == 1){
			qu.push({q , 1});
		}
		frz++;
		qu.pop();
		if(vis[u])	continue;
		vis[u] = 1;
		int cnt = 0;
		for(auto ed : ve[u]){
			int v = ed.v;
			if(du[v] > 1)	cnt++;
			if(!vis[v])	qu.push({v , io});
		}
		if(cnt > 2 && io){
			flag = 1;
			break;
		}
	}
	if(flag){
		cout << "Drifty" << '\n';
	}
	else{
		cout << "hgcnxn" << '\n';
	}
}

int main(){
	T = ra;
	while(T--){
		init();
		solve();
	}
	return 0;
}
2024/11/22 10:45
加载中...