一种新的暴力写法

PS：如果题解区或讨论区已有该解法则删帖
没看题解之前想出的一种特殊的暴力解法，我先想到的思路也是维护每个点的入度之和，但由于没想到哈希，每次如果发现出度和为n则暴力判是否满足每个点入度为1，具体地可使用时间戳+map来判某一条边是否存在，用于map常数过大可使用pbds库的cc_hash_table即可通过本题，代码如下：（码风诡异勿喷）\

CPP

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define scanf __builtin_scanf
#define printf __builtin_printf
#define puts __builtin_puts
#define px first
#define py second
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<bool,int> P;
const int N=500005;
//const int MOD=;
int n,m,q,deg[N],deg2[N],sum;
vector<int> a[N];
set<int> b_nw[N];
__gnu_pbds::cc_hash_table<ll,P> edge;
P w[N];
inline ll hsh(const int& x,const int& y){
	return ll(x-1)*n+y;
}
inline bool query(int x,int y){
	P t=edge[hsh(x,y)];
	return t.py>w[y].py?t.px:w[y].px;
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);
		++deg[v];
		++deg2[v];
		a[u].push_back(v);
		edge[hsh(u,v)]=mkp(1,0);
	}
	for(int i=1;i<=n;i++) sum+=deg[i],w[i]=mkp(1,0);
	scanf("%d",&q);
	for(int clk=1,t,u,v;clk<=q;clk++){
		scanf("%d%d",&t,&u);
		if(t&1) scanf("%d",&v);
		if(t==1) --deg2[v],--sum,edge[hsh(u,v)]=mkp(0,clk);
		if(t==3) ++deg2[v],++sum,edge[hsh(u,v)]=mkp(1,clk);
		if(t==2) sum-=deg2[u],deg2[u]=0,w[u]=mkp(0,clk);
		if(t==4) sum+=deg[u]-deg2[u],deg2[u]=deg[u],w[u]=mkp(1,clk);
		if(sum==n){
			for(int i=1;i<=n;i++){
				int cnt=0;
				for(int j:a[i]) if(query(i,j)) ++cnt;
				if(cnt!=1){
					puts("NO");
					goto TAG;
				}
			}
			puts("YES");
		}
		else puts("NO");
		TAG:;
	}
	return 0;
}

一种新的暴力写法

讨论操作

回复

相关推荐

一种新的暴力写法