问题标题: NOIP2023可以估分了

https://www.yundouxueyuan.com/contest/655873a8d44fd01b58750214

不知道为啥我T1暴力n^3居然A了

薛乘志在2023-11-18 17:26:36追加了内容

又：欢迎观赏我的T2注释

#include <bits/stdc++.h>
using namespace std;
/* 11:17 delete it
int n,m;
struct edge{
	int fa;
	char v;
};
edge fa[200005];
edge find(int x){
	if(x>100000) return fa[x];
	if(fa[x].fa==x) return fa[x];
	edge fx=find(fa[x].fa);
	if(fa[x].v=='+'&&fx.v=='+'||fa[x].v=='-'&&fx.v=='-'){
		fa[x]={fx.fa,'+'};
	}else if(fa[x].v=='+'&&fx.v=='-'||fa[x].v=='-'&&fx.v=='+'){
		fa[x]={fx.fa,'-'};
	}else{
		fa[x]={fx.fa,fa[x].v}; 
	}
	return fa[x];
}
void work(){
	for(int i=1;i<=n;i++){
		fa[100000+i]={100000+i,'X'};
	}
	fa[200000+1]={200000+1,'U'};
	fa[200000+2]={200000+2,'T'};
	fa[200000+3]={200000+3,'F'};
	for(int i=1;i<=n;i++){ //init
		fa[i]={100000+i,'+'};
	}
	for(int i=1;i<=m;i++){
		char v;
		cin>>v;
		if(v=='+'||v=='-'){
			int x,y;
			scanf("%d%d",&x,&y);
			fa[x]={y,v};
			find(x);
		}else{
			int x;
			scanf("%d",&x);
			if(v=='U'){
				fa[x]={200000+1,'+'};
			}else if(v=='T'){
				fa[x]={200000+2,'+'};
			}else if(v=='F'){
				fa[x]={200000+3,'+'};
			}
		}
	}
	int cnt=0;
	int req[100005]={};
	for(int i=1;i<=n;i++){
		cout<<i<<": "<<fa[i].fa<<" "<<fa[i].v<<endl;
		if(fa[i].fa==200000+1){
			cnt++;
		}else if(fa[i].fa>100000&&fa[i].fa<=200000){
			req[i]=fa[i].fa-100000;
		}
	}
	printf("%d\n",cnt);
}
*/
int n,m,a[100005];
const int U=100000+1,T=100000+2,F=100000+3;
struct edge{
	int v,w;
};
vector<edge> g[100005];
bool vis[100005],huan=false;
/*
void dfs(int u,int k){
	for(auto e:g[u]){
		if(e.v==-k*e.w) huan=true;
		if(vis[e.v]==0){
			vis[e.v]=1;
			dfs(e.v,k*e.w);
		}
	}
}*/
void bfs(int uu,int kk){
	struct node{
		int u,k;
	};
	queue<node> q;
	q.push({uu,kk});
	while(!q.empty()){
		auto h=q.front();
		q.pop();
		for(auto e:g[h.u]){
			if(e.v==-h.k*e.w){
				huan=true;
				return;
			}
			if(vis[e.v]==0){
				vis[e.v]=1;
				q.push({e.v,h.k*e.w});
			}
		}
	}
}
bool uk[100005];
/*
void color(int u){
	uk[u]=1;
	for(auto e:g[u]){
		if(uk[e.v]==0){
			color(e.v);
		}
	}
}*/
void bcolor(int uu){
	uk[uu]=1;
	queue<int> q;
	q.push(uu);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto e:g[u]){
			if(uk[e.v]==0){
				bcolor(e.v);
			}
		}
	}
}
void work(){
	memset(vis,0,sizeof(vis));
	memset(uk,0,sizeof(uk));
	for(int i=1;i<=n;i++){
		a[i]=i;
		g[i].clear();
	}
	for(int i=1;i<=m;i++){
		char v;
		cin>>v;
		if(v=='+'||v=='-'){
			int x,y;
			scanf("%d%d",&x,&y);
			if(v=='+') a[x]=a[y];
			else a[x]=-a[y];
		}else{
			int x;
			scanf("%d",&x);
			if(v=='U') a[x]=U;
			else if(v=='T') a[x]=T;
			else if(v=='F') a[x]=F;
		}
	}
	for(int i=1;i<=n;i++){
		if(i!=abs(a[i])) g[abs(a[i])].push_back({i,a[i]/abs(a[i])});
	}
	for(int i=1;i<=n;i++){
		huan=false;
		bfs(i,i);
		if(huan) bcolor(i);
	}
	for(int i=1;i<=n;i++){
		//cout<<i<<": "<<a[i]<<endl;
		if(a[i]==U||a[i]==-U){
			bcolor(i);
		}else if(a[i]==-i){
			bcolor(i);
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		cnt+=(uk[i]?1:0);
	}
	printf("%d\n",cnt);
}
int main(){
	freopen("tribool.in","r",stdin);
	freopen("tribool.out","w",stdout);
	int C,T;
	cin>>C>>T;
	while(T--){
		scanf("%d%d",&n,&m);
		work();
	}
	return 0;
}

薛乘志在2023-11-18 18:13:15追加了内容

洛谷也可以估了：https://www.luogu.com.cn/contest/145259