QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#530902 | #8551. DFS Order 5 | chenxinyang2006 | WA | 2ms | 9988kb | C++20 | 4.3kb | 2024-08-24 17:35:57 | 2024-08-24 17:35:57 |
Judging History
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'