QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749132 | #8551. DFS Order 5 | 000226# | WA | 32ms | 14584kb | C++17 | 3.8kb | 2024-11-14 22:47:23 | 2024-11-14 22:47:23 |
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 Seg{
struct tree{ int val,lazy; }tr[maxn<<2];
void Pushup(int rt){ tr[rt].val=tr[rt<<1].val+tr[rt<<1|1].val; }
void Build(int rt,int l,int r){
tr[rt].lazy=-1;
if(l==r)return;
int mid=(l+r)>>1;
Build(rt<<1,l,mid),Build(rt<<1|1,mid+1,r);
}
void Update(int rt,int l,int r,int w){
tr[rt].val=w*(r-l+1);
tr[rt].lazy=w;
}
void Pushdown(int rt,int l,int r){
if(tr[rt].lazy==-1)return;
int mid=(l+r)>>1;
Update(rt<<1,l,mid,tr[rt].lazy);
Update(rt<<1|1,mid+1,r,tr[rt].lazy);
tr[rt].lazy=-1;
}
void Modify(int rt,int l,int r,int s,int t,int w){
if(s<=l && t>=r)return Update(rt,l,r,w);
int mid=(l+r)>>1;
Pushdown(rt,l,r);
if(s<=mid)Modify(rt<<1,l,mid,s,t,w);
if(t>mid)Modify(rt<<1|1,mid+1,r,s,t,w);
Pushup(rt);
}
int Query(int rt,int l,int r,int s,int t){
if(s<=l && t>=r)return tr[rt].val;
int mid=(l+r)>>1,res=0;
Pushdown(rt,l,r);
if(s<=mid)res=Query(rt<<1,l,mid,s,t);
if(t>mid)res+=Query(rt<<1|1,mid+1,r,s,t);
return res;
}
}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 Lim;
int R;
bool Jump(int &u,int v,bool ch){
if(T.Query(1,1,n,dfn[v],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;
if((!ch) && (!Lim) && dep[lf]< dep[fa[u]] && T.Query(1,1,n,dfn[fa[u]]+1,dfn[fa[u]]+siz[fa[u]]-1)!=siz[fa[u]]-1)return false;
int p=Kth(u,dep[u]-dep[lf]-1);
if((!ch) && (!Lim)){
if(dep[lf]<dep[fa[u]] && T.Query(1,1,n,dfn[p]+1,dfn[p]+siz[p]-1)!=siz[p]-1)return false;
}
if(Lim){
if(dep[lf]<dep[R])R=lf;
else Lim=false;
}
T.Modify(1,1,n,dfn[p],dfn[p]+siz[p]-1,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);
T.Build(1,1,n);
while(q--){
int len;cin>>len;G.Lim=true;
int u;cin>>u;bool flag=true;G.R=u;
Rep(i,2,len){
T.Modify(1,1,n,G.dfn[u],G.dfn[u],1);
int v;cin>>v;
if(!flag)continue;
flag=G.Jump(u,v,i==2);
}
if(flag)cout<<"Yes\n";
else cout<<"No\n";
T.Update(1,1,n,0);
}
}
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: 3ms
memory: 12472kb
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: 32ms
memory: 14584kb
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'