QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#530902#8551. DFS Order 5chenxinyang2006WA 2ms9988kbC++204.3kb2024-08-24 17:35:572024-08-24 17:35:57

Judging History

你现在查看的是最新测评结果

  • [2024-08-24 17:35:57]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9988kb
  • [2024-08-24 17:35:57]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m;
vector <int> G[100005],son[100005];

int fa[100005],dfn[100005],siz[100005],dep[100005],ST[20][100005],Mn[20][100005],Mx[20][100005],N;
int anc(int u,int v){
	return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + siz[u];
}
void dfs(int u,int f){
	fa[u] = f;
	dfn[u] = ++N;
	dep[u] = dep[f] + 1;
	siz[u] = 1;
	for(int v:G[u]){
		if(v == f) continue;
		dfs(v,u);
		son[u].eb(v);
		siz[u] += siz[v];
	}
}
int k;
int a[100005],idx[100005];
inline int cmp(int x,int y){
	if(dep[x] != dep[y]){
		if(dep[x] < dep[y]) return x;
		return y;
	}
	if(idx[x] < idx[y]) return x;
	return y;
}

inline int qry(int l,int r){
	int x = __lg(r - l + 1);
	return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}

int chk(int u,int l,int r){
	int x = __lg(r - l + 1);
	return dfn[u] <= min(Mn[x][l],Mn[x][r - (1 << x) + 1]) && max(Mx[x][l],Mx[x][r - (1 << x) + 1]) < dfn[u] + siz[u];
}

int locate(int u,int v){
	assert(anc(u,v));
	int pos = 0;
	per(_k,16,0) if(pos + (1 << _k) < SZ(son[u]) && dfn[son[u][pos + (1 << _k)]] <= dfn[v]) pos += 1 << _k;
	return son[u][pos];
}

int concheck(int l,int r){
//	printf("concheck [%d,%d]\n",l,r);
	rep(i,l + 1,r) if(!anc(fa[a[i]],a[i - 1])) return 0;
	if(r - l + 1 != siz[a[l]]) return 0;
//	printf("suc\n");
	return 1;
}

int sz;
int b[100005];
int prefcheck(int l,int r){
//	printf("prefcheck [%d,%d]\n",l,r);
	int u = a[l],p,cur = l + 1;
	sz = 0;
	while(cur <= r){
		if(sz && dep[qry(cur,r)] != dep[a[b[1]]]) break;
		p = idx[qry(cur,r)];
		b[++sz] = p;
		if(fa[a[p]] != u) return 0;
		cur = p + 1;
	}
//	rep(i,1,sz) printf("%d ",b[i]);
//	printf("\n");
	rep(i,1,sz - 1) if(!concheck(b[i],b[i + 1] - 1)) return 0;
//	printf("%d\n",b[sz]);
	if(!sz) return 1;
	return prefcheck(b[sz],r);
}

int sufcheck(int l,int r){
//	printf("sufcheck [%d,%d]\n",l,r);
	int p,cur = l;
	sz = 0;
	while(cur <= r){
		if(sz && dep[qry(cur,r)] != dep[a[b[1]]]) break;
		p = idx[qry(cur,r)];
		b[++sz] = p;
		cur = p + 1;
	}
	b[sz + 1] = r + 1;
	rep(i,1,sz) if(fa[a[b[i]]] != fa[a[b[1]]] || !concheck(b[i],b[i + 1] - 1)) return 0;
//	printf("ovo %d %d\n",b[1],l);
	if(b[1] == l) return 1;
	if(!anc(fa[a[b[1]]],a[b[1] - 1])) return 0;
	int q = locate(fa[a[b[1]]],a[b[1] - 1]);
	if(!chk(q,l,b[1] - 1)) return 0;
	return sufcheck(l,b[1] - 1);
}

int solve(){
	rep(i,1,k){
		if(idx[a[i]]) return 0;
		idx[a[i]] = i;
		ST[0][i] = a[i];
		Mn[0][i] = Mx[0][i] = dfn[a[i]];
	}
	rep(i,2,k) if(anc(a[i],a[i - 1])) return 0;
	rep(i,1,16){
		rep(j,1,k){
			if(j + (1 << i) - 1 > k) break;
			ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
			Mn[i][j] = min(Mn[i - 1][j],Mn[i - 1][j + (1 << (i - 1))]);
			Mx[i][j] = max(Mx[i - 1][j],Mx[i - 1][j + (1 << (i - 1))]);			
		}
	}
	sz = 0;
	int cur = 1;
	while(cur <= k){
		if(sz && dep[qry(cur,k)] != dep[a[b[1]]]) break;
		b[++sz] = idx[qry(cur,k)];
		cur = b[sz] + 1;
	}
//	rep(i,1,sz) printf("%d ",b[i]);
//	printf("\n");
	rep(i,1,sz) if(fa[a[b[i]]] != fa[a[b[1]]]) return 0;
	rep(i,1,sz - 1) if(!concheck(b[i],b[i + 1] - 1)) return 0;
	if(!prefcheck(b[sz],k)) return 0;
	if(b[1] > 1) return sufcheck(1,b[1] - 1);
	return 1;
}

int main(){	
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	rep(i,1,n - 1){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].eb(v);G[v].eb(u);
	}
	dfs(1,0);
	rep(i,1,m){
		scanf("%d",&k);
		rep(s,1,k) scanf("%d",&a[s]);
		if(solve()) printf("Yes\n");
		else printf("No\n");
		rep(s,1,k) idx[a[s]] = 0;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9988kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
No
Yes
No

result:

wrong answer 7th words differ - expected: 'Yes', found: 'No'