MLE on #9,#10
查看原帖
MLE on #9,#10
579857
popossible楼主2024/5/2 11:09

rt

#include<bits/stdc++.h>
using namespace std;

//#define int ll
typedef long long ll;

#define mk make_pair
typedef pair<int,int> pii; 

const int N=6e5+100;
const int M=6e5+100;

int n,m,q;
map<pii ,int>mp;

struct edge{
	int to,net;
};

template<int Vertix,int Edge>
class graph {
	private :
		int cnt;
	public :
		edge ed[Edge];
		int hed[Vertix];
		
		#define Begin(id) hed[id]
		#define Nxt(id) ed[id].net
		#define To(id) ed[id].to
		
		void add(int x,int y) {
			ed[++cnt].net=hed[x];
			hed[x]=cnt;
			ed[cnt].to=y;
		}
		
		void link(int x,int y) {
			add(x,y);add(y,x);
		}
};
graph<N,M<<1>G;

namespace Round_Square_Tree {
	graph<N<<1,N<<2>T;
	int vn,stk[N],top=0;
	int dfn[N],low[N],ord,d[N];
//	int id[M],flag[M];
	map<int,int>id;
	
	void Tarjan(int now,int mf) {
		stk[++top]=now;
		dfn[now]=low[now]=++ord;
		for(int i=G.Begin(now);i;i=G.Nxt(i)) {
			int to=G.To(i);
			if(to==mf) continue;
			if(!dfn[to]) {
//				cout<<now<<" "<<to<<"\n";
				Tarjan(to,now);
				low[now]=min(low[now],low[to]);
				if(low[to]>=dfn[now]) {
					vn++;
					if(low[to]>dfn[now]) {
						id[(i-1)/2+1]=vn;
					}
//					cout<<vn<<":"<<now<<" ";
					
					T.link(vn,now);
					d[now]++;
					int u=0;
					for(;u!=to&&top;top--) {
						u=stk[top];
						T.link(vn,u);
						d[u]++;
//						cout<<u<<" ";
					}
//					cout<<"\n";
				}
			}
			else low[now]=min(low[now],dfn[to]);
		}
	}
	
	void Build_RST(int n) {
		vn=n;
		Tarjan(1,0);
	}
}using namespace Round_Square_Tree;

namespace Tree_Chain{
	int siz[N],fa[N];
	int dept[N],top[N],son[N];
	int id[N],ord;
	
	void dfs1(int now,int mf) {
		fa[now]=mf;dept[now]=dept[mf]+1;
		siz[now]=1;
		for(int i=T.Begin(now);i;i=T.Nxt(i)) {
			int to=T.To(i);
			if(to==mf) continue;
			dfs1(to,now);
			siz[now]+=siz[to];
			siz[to]>siz[son[now]]?son[now]=to:1;
		} 
	}
	
	void dfs2(int now,int topf) {
		id[now]=++ord;
		top[now]=topf;
		if(son[now]) dfs2(son[now],topf) ;
		for(int i=T.Begin(now);i;i=T.Nxt(i)) {
			int to=T.To(i);
			if(to==fa[now]||to==son[now]) continue;
			dfs2(to,to);
		} 
	}
	
	int query(int x,int y,int z) {
		while(top[x]!=top[y]) {
			if(dept[top[x]]<dept[top[y]]) swap(x,y);
			if(id[top[x]]<=id[z]&&id[z]<=id[x]) return 1;
			x=fa[top[x]];
		}
//		cout<<x<<" "<<y<<"\n";
		if(dept[x]>dept[y]) swap(x,y);
		if(id[x]<=id[z]&&id[z]<=id[y]) return 1;
		return 0;
	}
	
	void Build_TrChain() {
		dfs1(1,0);
		dfs2(1,1);
	}
	
}
#define TC Tree_Chain
//using namespace Tree_Chain;

signed main(){
	
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x,y;
		cin>>x>>y;
		G.link(x,y);
		mp[mk(x,y)]=mp[mk(y,x)]=i;
	}
//	cout<<"\n";
	Build_RST(n);
//	cout<<"\n"; 
	Tree_Chain::Build_TrChain();
	
	cin>>q;
	for(int i=1;i<=q;i++) {
		int opt;
		cin>>opt;
		if(opt==1) {
			int a,b,x,y;
			cin>>a>>b>>x>>y;
			int e=mp[mk(x,y)];
//			cout<<e<<"\n";
			if(!e) cout<<"error\n";
			else if(!id[e]) cout<<"yes\n";
			else cout<<(Tree_Chain::query(a,b,id[e])?"no\n":"yes\n");
			continue;
		}
		if(opt==2) {
			int x,y,z;
			cin>>x>>y>>z;
			if(d[z]==0) cout<<"error\n";
			else if(d[z]==1) cout<<"yes\n";
			else cout<<(TC::query(x,y,z)?"no\n":"yes\n");
			continue;
		}
	}
	
	return 0;
}
2024/5/2 11:09
加载中...