rt,样例第五个询问会输出 Yes,但是已 AC 。提交记录。
#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;
}