QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#748733 | #8551. DFS Order 5 | 000226# | WA | 26ms | 13780kb | C++17 | 2.4kb | 2024-11-14 21:14:37 | 2024-11-14 21:14:38 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=1e5+10;
int n,q;
set<int>S[maxn];
struct BIT{
int c[maxn];
vector<pii>vec;
void Add(int x,int d){
for(;x<=n;x+=lowbit(x))c[x]+=d;
}
int Query(int x){
int res=0;for(;x;x-=lowbit(x))res+=c[x];
return res;
}
void Clear(){ for(auto it : vec)Add(it.fir,it.sec); vec.resize(0); }
}T;
struct Graph{
vector<int>E[maxn];
void lqx(int u,int v){ E[u].emplace_back(v);S[u].insert(v); }
int fa[maxn],top[maxn],siz[maxn],dfn[maxn],Te,rk[maxn],son[maxn],dep[maxn];
void Dfs1(int u){
siz[u]=1;dep[u]=dep[fa[u]]+1;
for(auto v :E[u])if(v!=fa[u]){
fa[v]=u;Dfs1(v);siz[u]+=siz[v];
if(!son[u] || siz[v]>siz[son[u]])son[u]=v;
}
}
void Dfs2(int u,int tp){
top[u]=tp;dfn[u]=++Te;rk[Te]=u;
if(son[u])Dfs2(son[u],tp);
for(auto v : E[u])if(v!=fa[u] && v!=son[u]){
Dfs2(v,v);
}
}
int Lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v] ? u : v;
}
int Kth(int u,int k){
while(k){
if(k>=dep[u]-dep[top[u]]){
k-=(dep[u]-dep[top[u]]);
u=top[u];
}else {
return rk[dfn[u]-k];
}
if(!k)break;
--k;u=fa[u];
}
return u;
}
bool Jump(int &u,int v){
if(T.Query(dfn[v]))return false;
int lf=Lca(u,v);
if(lf==v)return false;
if(lf==u){
if(S[u].count(v))return u=v,true;
else return false;
}
if((E[u].size()>1))return false;
if(!S[lf].count(v))return false;
int p=Kth(u,dep[u]-dep[lf]-1);
T.Add(dfn[p],1);T.vec.emplace_back(dfn[p],-1);
T.Add(dfn[p]+siz[p],-1);T.vec.emplace_back(dfn[p]+siz[p],1);
u=v;return true;
}
}G;
void solve(){
cin>>n>>q;Rep(i,2,n){ int u,v;cin>>u>>v;G.lqx(u,v),G.lqx(v,u); }
G.Dfs1(1),G.Dfs2(1,1);
while(q--){
int len;cin>>len;
int u;cin>>u;bool flag=true;
Rep(i,2,len){
int v;cin>>v;
if(!flag)continue;
flag=G.Jump(u,v);
}
if(flag)cout<<"Yes\n";
else cout<<"No\n";
T.Clear();
}
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 11840kb
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 Yes
result:
ok 7 tokens
Test #2:
score: -100
Wrong Answer
time: 26ms
memory: 13780kb
input:
10 100000 7 2 1 7 7 10 8 6 8 7 1 3 4 5 9 5 5 8 8 8 9 7 2 8 1 6 1 4 8 3 5 2 6 7 10 3 9 9 1 1 1 8 10 3 2 9 3 8 7 3 7 5 6 2 8 5 9 1 6 3 4 6 2 1 3 5 8 9 2 4 9 1 3 2 1 5 5 8 5 1 7 9 10 5 2 9 2 6 4 10 6 3 8 3 4 5 8 2 8 4 9 4 10 1 2 4 3 3 6 3 1 3 6 1 1 6 8 3 1 3 7 3 2 3 9 1 5 4 3 7 8 10 9 4 2 3 10 2 5 4 3 ...
output:
No No No Yes No No No No Yes No No No No No No Yes No No No No No No No No No No No No No No No Yes No No No No No No Yes No No No No No Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No Yes No No Yes Yes No No No No Yes No No No No No No No No No No No No No No No No N...
result:
wrong answer 899th words differ - expected: 'No', found: 'Yes'