和这题数据爆了
查看原帖
和这题数据爆了
365021
masterhuang楼主2024/5/25 21:52

首先目前所有通过做法都不是正解。

这题数据有如下两个问题:

  1. 图存在重边
  2. 存在一条边被删两次,题意没有说清楚这种情况咋办

按照自己认为的正解写是无法通过本题的,原因如下:

姑且认为一条边删除多次等价于删除一次。

根据哈希做法,最终要判断一些数 xor 起来是否为 0,但是如果删除了一条边两次,就会出现相同的哈希值两次,天然产生 xor 为 0,但是有时候显然并不是这样的。

至于数据咋修改,我也不知道,这tm锅太大了,如果有佬有兴趣验证我“正解”的正确性的话可以拿我代码重新跑一遍数据。

//洛谷 P10075
//https://www.luogu.com.cn/problem/P10075
#include<bits/stdc++.h>
#define LL long long
#define u64 unsigned long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937_64 rnd(time(0));
const int N=1e6+5;
int n,m,q,B[9],b[9],tot=1,cnt,head[N],to[N],c[N];u64 a[N],w[N],s[25];bool v[N];
struct edge{int to,nex;}e[N<<1];
map<pair<int,int>,int>mp;
inline void add(int u,int v,int i)
{
	if(u>v) swap(u,v);
	if(mp[{u,v}]) return c[to[i]=mp[{u,v}]]++,void();c[to[i]=mp[{u,v}]=++cnt]=1;
	e[++tot]={v,head[u]};head[u]=tot;
	e[++tot]={u,head[v]};head[v]=tot;
}
void dfs(int x,int fa)
{
	v[x]=1;
	for(int i=head[x];i;a[x]^=w[i>>1],i=e[i].nex)
	{
		int y=e[i].to;
		if(y^fa)
		{
			if(v[y]&&!w[i>>1]) w[i>>1]=rnd();
			else if(!v[y]) dfs(y,x),w[i>>1]=a[y];
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
	for(int i=1,u,v;i<=m;i++) cin>>u>>v,add(u,v,i);dfs(1,0);cin>>q;
	while(q--)
	{
		int k=0,K;cin>>K;for(int i=0;i<K;i++) cin>>B[i];
		sort(B,B+K);K=unique(B,B+K)-B;
		for(int i=0;i<K;i++) B[i]=to[B[i]];
		for(int i=0;i<K;i++) if(!--c[B[i]]) b[k++]=B[i];
		for(int i=1;i<(1<<k);i++) s[i]=s[i-(1<<__lg(i))]^w[b[__lg(i)]];
		cout<<((!k||*min_element(s+1,s+(1<<k)))?"ymqOAO":"Bob")<<"\n";
		for(int i=0;i<K;i++) c[B[i]]++;
	}
	return 0;
}
2024/5/25 21:52
加载中...