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;
}