过不了样例的 AC 真合理
查看原帖
过不了样例的 AC 真合理
123796
封禁用户楼主2021/8/15 09:54

rtrt,样例第五个询问会输出 Yes\rm Yes,但是已 ACAC提交记录

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
// #include <ctime>
// clock_t __start_time;
using namespace std;
typedef long long int_;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(register int i=(a); i>=(b); --i)
const int __buffer_length = 2300000;
char read_buf[__buffer_length];
inline char getChar(){
	static char *S = read_buf, *T = S;
	if(S == T) S = read_buf, T = S +
		fread(S,1,__buffer_length,stdin);
	return *(S ++); // no more check
}
inline int readint(){
	int a = 0; char c = getChar(), f = 1;
	for(; c<'0'||c>'9'; c=getChar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getChar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MaxN = 50005;
const int MaxM = 100005;
struct Edge{
	int from, to, val[2], id;
	bool operator < (const Edge &t) const {
		return val[0] < t.val[0];
	}
};
Edge e[MaxM], ask[MaxN];
bool ans[MaxN];
int n, m, q;

const int Step = 1400; // block length
const int Count = MaxM/Step+1;
// const int Count = 1000;
struct UFS{
	int fa[MaxN], val[MaxN];
	int good[MaxN]; // count good
	void init(){
		rep(i,1,n){
			fa[i] = i, val[i] = 1;
			good[i] = 0;
		}
	}
	inline int find_stable(int a){
		// for(; fa[a]^a; a=fa[a]);
		if(fa[a]^a) // fa[a] != a
			return find_stable(fa[a]);
		else return a;
	}
	inline int find(int a){
		if(fa[a]^a)
			fa[a] = find(fa[a]);
		return fa[a];
	}
	void tap(int a,int v){
		good[find(a)] += v;
	}
	void tap_stable(int a,int v){
		good[find_stable(a)] += v;
	}
	void merge(int a,int b){
		a = find(a), b = find(b);
		if(a == b) return ;
		if(val[a] > val[b])
			a ^= b ^= a ^= b;
		fa[a] = b, val[b] += val[a];
	}
	vector<int> sta;
	void merge_stable(int a,int b){
		a = find_stable(a);
		b = find_stable(b);
		if(a == b){
			sta.push_back(0);
			return ;
		}
		if(val[a] > val[b])
			a ^= b ^= a ^= b;
		fa[a] = b, val[b] += val[a];
		sta.push_back(a);
		good[b] += good[a];
	}
	void stepBack(){
		int a = sta.back();
		sta.pop_back();
		if(a == 0) return ;
		val[fa[a]] -= val[a];
		good[fa[a]] -= good[a];
		fa[a] = a;
	}
};
UFS ufs[Count];

int tmp[MaxM]; // LiSanHua
int haxi[MaxM]; // hash
void addEdge(int id){
	int p = haxi[id]/Step+1;
	rep(i,p,m/Step) // prefix sum
		ufs[i].merge(e[id].from,e[id].to);
}
void turnOn(int id,int v){
	int p = haxi[id]/Step+1;
	rep(i,p,m/Step)
		ufs[i].tap(e[id].to,v);
}

/** @param b When inquire with e[tmp[b]].val[1] */
bool query(int a,int b,int S,int T){
	const int p = b/Step; // previous block
	// printf(">> query(%d,%d,%d,%d) = ",a,b,S,T);
	register int ass = max(p*Step,1);
	rep(i,ass,b){
		ufs[p].find(e[tmp[i]].from);
		ufs[p].find(e[tmp[i]].to);
	}
	ufs[p].sta.clear();
	rep(i,ass,b){
		if(e[tmp[i]].val[0] > a) continue;
		ufs[p].merge_stable(
			e[tmp[i]].from,e[tmp[i]].to);
		if(e[tmp[i]].val[0] == a)
			ufs[p].tap_stable(e[tmp[i]].to,1);
	}
	S = ufs[p].find_stable(S);
	bool res = (ufs[p].good[S] > 0)
		and (ufs[p].find_stable(T) == S);
	drep(i,b,ass){
		if(e[tmp[i]].val[0] > a) continue;
		if(e[tmp[i]].val[0] == a)
			ufs[p].tap_stable(e[tmp[i]].to,-1);
		ufs[p].stepBack();
	}
	return res;
}

bool cmp(const int &a,const int &b){
	return e[a].val[1] < e[b].val[1];
}
int sy[MaxM]; // for lower_bound
void solve(){
	rep(i,0,m/Step) ufs[i].init();
	sort(e+1,e+m+1); sy[0] = -1;
	rep(i,1,m) tmp[i] = i;
	sort(tmp+1,tmp+m+1,cmp);
	rep(i,1,m){
		haxi[tmp[i]] = i;
		sy[i] = e[tmp[i]].val[1];
		// printf("tmp[%d] = %d (%d %d %d %d)\n",i,tmp[i],
		// 	e[tmp[i]].from,e[tmp[i]].to,e[tmp[i]].val[0],e[tmp[i]].val[1]);
	}
	sort(ask+1,ask+q+1); int l = 1, r = 1;
	// printf("Checkpoint 1: %ldms\n",clock()-__start_time);
	// clock_t __query_time = 0;
	for(int qid=1; l<=m&&qid<=q; l=r){
		for(; qid<=q&&!ans[ask[qid].id]; ++qid);
		if(qid == q+1) break; // done all
		while(l <= m && e[l].val[0] < ask[qid].val[0])
			addEdge(l ++); // find ask[qid].val[0]
		if(l == m+1) break; // not found
		if(e[l].val[0] > ask[qid].val[0]){
			ans[ask[qid].id] = false;
			++ qid; continue;
		}
		for(r=l; r<=m&&e[r].val[0]==e[l].val[0]; )
			addEdge(r ++); // [l,r) the same
		rep(i,l,r-1) turnOn(i,1);
		for(; qid<=q&&ask[qid].val[0]==e[l].val[0]; ){
			int rnk = lower_bound(sy+1,
				sy+m+1,ask[qid].val[1]+1)-sy-1;
			if(sy[rnk] != ask[qid].val[1]) // not found
				ans[ask[qid].id] = false;
			// __query_time -= clock();
			ans[ask[qid].id] = ans[ask[qid].id]
				and query(ask[qid].val[0],rnk,
					ask[qid].from,ask[qid].to);
			// __query_time += clock();
			++ qid; // advance
		}
		drep(i,r-1,l) turnOn(i,-1);
	}
	// printf("Query in total: %ldms\n",__query_time);
	// printf("Checkpoint 2: %ldms\n",clock()-__start_time);
}

int main(){
	// freopen("data.in","r",stdin);
	// freopen("my.out","w",stdout);
	// __start_time = clock();
	n = readint(), m = readint();
	for(int i=1; i<=m; ++i){
		e[i].from = readint();
		e[i].to = readint();
		e[i].val[0] = readint();
		e[i].val[1] = readint();
	}
	q = readint();
	rep(i,1,q){
		ask[i].from = readint();
		ask[i].to = readint();
		ask[i].val[0] = readint();
		ask[i].val[1] = readint();
		ask[i].id = i, ans[i] = 1;
	}
	solve(); // for val[0]
	rep(i,1,m){
		e[i].val[0] ^= e[i].val[1];
		e[i].val[1] ^= e[i].val[0];
		e[i].val[0] ^= e[i].val[1];
	}
	rep(i,1,q){
		ask[i].val[0] ^= ask[i].val[1];
		ask[i].val[1] ^= ask[i].val[0];
		ask[i].val[0] ^= ask[i].val[1];
	}
	solve(); // for val[1]
	rep(i,1,q) puts(ans[i] ? "Yes" : "No");
	// fprintf(stderr,"%ldms\n",clock()-__start_time);
	return 0;
}
2021/8/15 09:54
加载中...