https://codeforces.com/gym/102055/problem/B
训练的时候队友WA K太久了这题我口胡完了没写完。
补题发现卧槽巨卡空间，stl空间常数巨大，底层都是vector，vector自带3倍空间常数，然后又不知道有其他的什么空间消耗= =
本来用了两个priority_queue套了一堆pair然后mle
然后换成了pair的multiset又mle
最后multiset<int> 过了，我透
首先，限制成环比impossible，可以使用虚点并查集判断，x,y在不同边相当于x 和 y+n ，x+n 和 y 连边，如果x y在某时属于同一个并查集那么必定成环了。
然后去dfs没成环的树，这种type=2，有两种情况，要么选mx[0] mx[1]为最大最小值，要么选mi[0] mx[1]为最大最小值。
如果是单个点就是type=1，要么选 mx[0] 要么选 mi[0]作为他的能力值。
我们先全选最大，这样保证在当前最大值下，最小值也最大，那么对于当前的最大值，最大值-最小值就是当前的答案。
接下来我们考虑到，如果不变化这个最大值，怎么变最小值只会变小，答案不会更优
所以我们考虑减小这个最大值，
如果是tp=1，那么就变成mi[0]
如果是tp=2，那么就变成mi[0],mi[1]
我们要一步一步减小最大值，所以要按照mx[0]从大到小排序。
考虑一下细节，当我们dfs树的时候。得到两组最大值最小值，由于我们一开始在最初情况下想让最小值最大，所以如果mx[1]>mx[1]则交换着两组值。
#include<bits/stdc++.h> #define maxl 200010 using namespace std; int n,m,cnt,tot,cas=0,ans; int f[maxl*2],ehead[maxl]; int mx[2],mi[2]; struct ed { int to,nxt; }e[maxl*2]; struct node { int l,d; }a[maxl]; struct nod { int tp; int mx[2],mi[2]; }b[maxl]; int st[maxl]; bool vis[maxl]; multiset <int> s; inline int find(int x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } inline void add(int u,int v) { e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt; } inline void dfs(int u,int k,int fa) { vis[u]=true; if(k==0) { mx[0]=max(mx[0],a[u].l); mx[1]=min(mx[1],a[u].l); mi[0]=max(mi[0],a[u].d); mi[1]=min(mi[1],a[u].d); } else { mx[0]=max(mx[0],a[u].d); mx[1]=min(mx[1],a[u].d); mi[0]=max(mi[0],a[u].l); mi[1]=min(mi[1],a[u].l); } int v; for(int i=ehead[u];i;i=e[i].nxt) { v=e[i].to; if(v==fa || vis[v]) continue; dfs(v,k^1,u); } } inline void prework() { ans=2e9; scanf("%d%d",&n,&m); for(int i=1;i<=n*2;i++) f[i]=i; for(int i=1;i<=n;i++) ehead[i]=0,vis[i]=false; int x,y,xx,yy; cnt=0; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(find(x)==find(y)) { ans=-1; continue; } xx=find(x);yy=find(y+n); if(f[yy]!=xx) f[yy]=xx; xx=find(x+n);yy=find(y); if(f[yy]!=xx) f[yy]=xx; add(x,y);add(y,x); } for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].d); if(ans==-1) return; tot=0; for(int i=1;i<=n;i++) if(!vis[i]) { if(ehead[i]==0) { vis[i]=true; ++tot;b[tot].tp=1; b[tot].mx[0]=max(a[i].l,a[i].d); b[tot].mi[0]=min(a[i].l,a[i].d); } else { mx[0]=0;mx[1]=2e9; mi[0]=0;mi[1]=2e9; dfs(i,0,0); if(mi[1]>mx[1]) swap(mx[0],mi[0]),swap(mx[1],mi[1]); ++tot;b[tot].tp=2; b[tot].mx[0]=mx[0];b[tot].mx[1]=mx[1]; b[tot].mi[0]=mi[0];b[tot].mi[1]=mi[1]; } } } inline bool cmp(const nod &x,const nod &y) { return x.mx[0]>y.mx[0]; } inline void mainwork() { if(ans==-1) return; s.clear(); sort(b+1,b+1+tot,cmp); for(int i=1;i<=tot;i++) if(b[i].tp==1) { st[i]=1; s.insert(b[i].mx[0]); } else { st[i]=1; s.insert(b[i].mx[0]); s.insert(b[i].mx[1]); } int id; for(int i=1;i<=tot;i++) { ans=min(ans,(*s.rbegin())-(*s.begin())); if(b[i].tp==1) { st[i]=2; s.erase(s.find(b[i].mx[0])); s.insert(b[i].mi[0]); } else { st[i]=2; s.erase(s.find(b[i].mx[0])); s.erase(s.find(b[i].mx[1])); s.insert(b[i].mi[0]); s.insert(b[i].mi[1]); } } ans=min(ans,(*s.rbegin())-(*s.begin())); } inline void print() { ++cas; if(ans==-1) printf("Case %d: IMPOSSIBLE\n",cas); else printf("Case %d: %d\n",cas,ans); } int main() { //freopen("B.in","r",stdin); int t; scanf("%d",&t); for(int i=1;i<=t;i++) { prework(); mainwork(); print(); } return 0; }
