数据好弱
  • 板块P2713 罗马游戏
  • 楼主ande
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/16 20:05
  • 上次更新2023/10/27 02:45:00
查看原帖
数据好弱
573589
ande楼主2022/11/16 20:05

RT 下方明显错误代码获得了60分的好成绩,造数据的人可能没想到有人会在这道题打暴力错解吧

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define P pair<int,int>
const int N = 1e6 + 10;
int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = x * 10 + (ch - 48); ch = getchar();}
	return x * f;	
}
int n, m, s;
struct aa{
	int to,next;
}edge[N * 2];
int head[N * 2], t = 1;
bool a[N];
int val[N];
void add(int now,int to){
	edge[t].to =  to;
	edge[t].next = head[now];
	head[now] = t++;
}
int fa[N];
int find(int a){
	if(fa[a] == a)return a;
	else return fa[a] = find(fa[a]);
}
void merge(int a,int b){
	int aa = find(fa[a]),bb = find(fa[b]);
	fa[aa] = bb;
	return;
}
int maxx,type;
int dfs(int now,int fa){
	if(maxx > val[now] )
		maxx = min(maxx,val[now]),type = now;
	for(int i = head[now];i;i = edge[i].next){
		int to_ = edge[i].to;
		if(to_ == fa || a[now] != false)continue;
		dfs(to_,now);
	}
}
signed main(){
n = read();
for(int i = 1;i<=n;i++){
	val[i] = read(),a[i] = true,fa[i] = i;
}
m = read();
while(m--){
	char x;
	cin>>x;
	if(x == 'M'){
		int y = read(), z = read();
		if(a[y] == false || a[z] == false || find(y) == find(z))continue;
		add(y,z),add(z,y);merge(y,z);
	}
	else{
		int y = read();maxx = 0x7ffffffff; type = 0;
		if(a[y] != false)
			dfs(y,0), a[type] = false;
		else maxx = 0;
		printf("%lld\n",maxx);
	}

}
	
	return 0;
}

2022/11/16 20:05
加载中...