ZOJ 3261. Connections in Galaxy War

链接

https://zoj.pintia.cn/problem-sets/91827364500/problems/91827368062

题意

$n$ 个点，每个点都有权值，给出 $m$ 条双向边，并有 $q$ 个操作

操作 destroy：断开 $x,y$ 之间的边

操作 query：询问与 $x$ 连通的点（不包括 $x$）中点权最大并且标号最小的点

思路

先将所有操作完后没有断开的边建立

逆向枚举 $q$ 个操作，如果遇到 destroy，则说明在此操作之前这条边存在，建立这条边

所有点的连通关系可以用并查集维护，在合并时，点权大并且标号小的点作为祖先

代码

#include<bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=1e4+5;
int a[N],fa[N];
map<PII,bool> mp;
VI res;
struct Q {char c;int x,y;Q() {}Q(char c,int x,int y):c(c),x(x),y(y) {}
}q[N*5];
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y) {int tx=find(x),ty=find(y);if(tx==ty) return;if(a[tx]>a[ty]||a[tx]==a[ty]&&tx<ty) fa[ty]=tx;else fa[tx]=ty;
}
int main() {int n;bool f=false;while(~scanf("%d",&n)) {mp.clear();res.clear();for(int i=0;i<n;i++) fa[i]=i;for(int i=0;i<n;i++) scanf("%d",&a[i]);int m;scanf("%d",&m);for(int i=1;i<=m;i++) {int x,y;scanf("%d%d",&x,&y);if(x>y) swap(x,y);mp[MP(x,y)]=true;}int o;scanf("%d",&o);char s[20];for(int i=1;i<=o;i++) {scanf("%s",s);if(s[0]=='q') {int x;scanf("%d",&x);q[i]=Q('q',x,-1);}else {int x,y;scanf("%d%d",&x,&y);if(x>y) swap(x,y);mp[MP(x,y)]=false;q[i]=Q('d',x,y);}}for(auto it:mp) {if(it.second==true) {int x=it.first.first,y=it.first.second;merge(x,y);}}for(int i=o;i>=1;i--) {if(q[i].c=='q') {int tx=find(q[i].x);if(a[tx]>a[q[i].x]) res.PB(tx);else res.PB(-1);}else merge(q[i].x,q[i].y);}if(f) puts("");else f=true;for(int i=SZ(res)-1;i>=0;i--) printf("%d\n",res[i]);}return 0;
}