QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#808324 | #8551. DFS Order 5 | ucup-team2179 | WA | 0ms | 9940kb | C++23 | 2.8kb | 2024-12-10 19:50:10 | 2024-12-10 19:50:14 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int maxn=300050;
int par[maxn][22];
int dep[maxn];
int siz[maxn];
int C=20;
int L[maxn];
int R[maxn];
int cnt=0;
vector<int> a[maxn];
void dfs(int u,int pre) //根节点深度为1
{
dep[u]=dep[pre]+1;
cnt++;
L[u]=cnt;
par[u][0]=pre;
siz[u]=1;
for(int i=1;i<C;i++)
{
par[u][i]=par[par[u][i-1]][i-1];
}
for(auto p:a[u])
{
if(p==pre)
continue;
dfs(p,u);
siz[u]+=siz[p];
}
R[u]=cnt;
}
int lca(int x,int y)
{
if(dep[y]>dep[x])swap(x,y);
for(int i=C-1;i>=0;i--)
{
if(dep[par[x][i]]>=dep[y])
x=par[x][i];
}
if(x==y)return y;
for(int i=C-1;i>=0;i--)
if(par[x][i]!=par[y][i])
{
x=par[x][i];
y=par[y][i];
}
return par[x][0];
}
int LCA(int u, int v) {
return lca(u, v);
}
struct stable {
vector<vector<int>> mylist;
int n;
int (*op) (int a, int b);
stable(vector<int>&a, int(*f)(int, int)) {
op = f;
n = a.size() - 1;
mylist = vector<vector<int>> (n + 1, vector<int>(__lg(n) + 1));
for (int i = 1; i <= n; i++) mylist[i][0] = a[i];
for (int j = 1; j <= __lg(n); j++)
for (int i = 1; i <= n - (1 << j) + 1; i++)
mylist[i][j] = op(mylist[i][j - 1], mylist[i + (1 << j - 1)][j - 1]);
}
int q(int l, int r) {
assert(l >= 1 && r <= n && l <= r);
int len = __lg(r - l + 1);
return op(mylist[l][len], mylist[r - (1 << len) + 1][len]);
}
};
void solve() {
int n, q; cin >> n >> q;
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1, 0);
while (q--) {
int k; cin >> k;
set<int> s;
vector<int> arr(k + 1);
for (int i = 1; i <= k; i++) cin >> arr[i], s.insert(arr[i]);
if (s.size() != k) {
cout << "No\n";
continue;
}
s.clear();
stable st(arr, LCA);
int flag = 1;
// for (int i = 1; i < k && flag; i++)
// flag &= (LCA(arr[i], arr[i + 1]) == par[arr[i + 1]][0]);
for (int i = 1; i <= k && flag; i++) {
flag &= (arr[i] == st.q(i, min(k, i + siz[arr[i]] - 1)));
}
for (int i = 1; i <= k && flag; i++) {
if(s.lower_bound(L[arr[i]])!=s.end()&&*s.lower_bound(L[arr[i]])<=R[arr[i]])flag=0;
s.insert(L[arr[i]]);
}
if (flag) cout << "Yes\n";
else cout << "No\n";
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9940kb
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 Yes Yes Yes
result:
wrong answer 5th words differ - expected: 'No', found: 'Yes'