【0】做题心得 - 2025 NOIP #64 - T2【bitset】

离正解就差一个 bitset。你会发现一个性质就是直接把确定发生的往下扔一定是对的，要是一个已经发生了且它的前驱没有一个是可以不经过

v

就能发生，那么显然此时会导致

v

自己也是对的。这个写出来容易做到

\mathcal O(nm+qn^2)

，超时。发现数据范围不是人

2\times 10^9

有两只怎么办呢发现经典 bitset 哦这扯不扯。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+10;
int n,m,q,deg[2][N];
bitset<N>ans,upset[N],downset[N];
vector<int>e[N],g[N];
queue<int>Q;
int main(){
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v), deg[0][v]++;
		g[v].push_back(u), deg[1][u]++;
	}
	for(int i=1;i<=n;i++)if(!deg[1][i])
		Q.push(i);
	while(Q.size()){
		int p=Q.front();
		Q.pop();
		upset[p][p]=1;
		for(auto v:g[p]){
			if(!(--deg[1][v]))Q.push(v);
			upset[v]|=upset[p];
		}
	}
	for(int i=1;i<=n;i++)if(!deg[0][i])
		Q.push(i);
	else
		downset[i].set();
	while(Q.size()){
		int p=Q.front();
		Q.pop();
		downset[p]|=upset[p];
		for(auto v:e[p]){
			if(!(--deg[0][v]))Q.push(v);
			downset[v]&=downset[p];
		}
	}
	while(q--){
		int k;
		cin>>k;
		ans.reset();
		while(k--){
			int p;
			cin>>p;
			ans|=downset[p];
		}
		for(int i=1;i<=n;i++)
			if(ans[i]) cout<<i<<" ";
		cout<<"\n";
	}
	return 0;
}

【0】做题心得 - 2025 NOIP #64 - T2【bitset】

文章操作

相关推荐

评论

【0】做题心得 - 2025 NOIP #64 - T2【bitset】