QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#115138 | #3501. Jail | c20230139 | 0 | 23ms | 45896kb | C++14 | 3.0kb | 2023-06-24 17:21:51 | 2023-06-24 17:21:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=5e5+5;
vector<int>e[N],E[N];
struct scan{
int s,t;
}a[N];
int top[N],du[N],dfn[N],son[N],size[N],tot,lson[N],rson[N],line[N],fa[N],dep[N];
void add(int u,int v) {
E[u].push_back(v);
du[v]++;
}//线段树建DAG
void build1(int &rt,int l,int r) {
rt=++tot;
if(l==r) return;
build1(lson[rt],l,mid);
build1(rson[rt],mid+1,r);
add(lson[rt],rt);
add(rson[rt],rt);
}//入树
void build2(int &rt,int l,int r) {
rt=++tot;
if(l==r) return;
build2(lson[rt],l,mid);
build2(rson[rt],mid+1,r);
add(rt,lson[rt]);
add(rt,rson[rt]);
}//出树
void update1(int rt,int l,int r,int x,int y){
if(l==r) return add(y,rt);
if(x<=mid) update1(lson[rt],l,mid,x,y);
else update1(rson[rt],mid+1,r,x,y);
}
void update2(int rt,int l,int r,int x,int y){
if(l==r) return add(rt,y);
if(x<=mid) update2(lson[rt],l,mid,x,y);
else update2(rson[rt],mid+1,r,x,y);
}
//单点
void query1(int rt,int l,int r,int x,int y,int z){
if(l>y||r<x) return;
if(x<=l && r<=y) return add(rt,z);
query1(lson[rt],l,mid,x,y,z);query1(rson[rt],mid+1,r,x,y,z);
}
void query2(int rt,int l,int r,int x,int y,int z){
if(l>y||r<x) return;
if(x<=l&&r<=y) return add(z,rt);
query2(lson[rt],l,mid,x,y,z);query2(rson[rt],mid+1,r,x,y,z);
}
//区间修改
void dfs1(int u) {
son[u]=0;
size[u]=1;
for(auto v:e[u]) {
if(v==fa[u]) continue;
fa[v]=u;
dep[v]=dep[u]+1;
dfs1(v);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u) {
dfn[u]=++tot;
if(u==son[fa[u]]) top[u]=top[fa[u]];
else top[u]=u;
if(son[u]) dfs2(son[u]);
for(auto v:e[u]) {
if(v==fa[u]||v==son[u])continue;
dfs2(v);
}
}//树链剖分
void solve() {
int n,m,rt1=0,rt2=0;
scanf("%d",&n);
for(int i=1,u,v;i<n;i++) {
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1);
dfs2(1);
scanf("%d",&m);
tot=m;
build1(rt1,1,n);
build2(rt2,1,n);
for(int i=1;i<=m;i++) scanf("%d%d",&a[i].s,&a[i].t);
// for(int i=1;i<=m;i++) update1(rt1,1,n,dfn[a[i].s],i),update2(rt2,1,n,dfn[a[i].t],i);
for(int u,v,i=1;i<=m;i++){
u=a[i].s;v=a[i].t;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
query1(rt1,1,n,dfn[top[u]]/*+(top[u]==a[i].s)*/,dfn[u]/*-(u==a[i].s)*/,i);
query2(rt2,1,n,dfn[top[u]]/*+(top[u]==a[i].t)*/,dfn[u]/*-(u==a[i].t)*/,i);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
query1(rt1,1,n,dfn[u]/*+(u==a[i].s)*/,dfn[v]/*-(v==a[i].s)*/,i);
query2(rt2,1,n,dfn[u]/*+(u==a[i].t)*/,dfn[v]/*-(v==a[i].t)*/,i);
}
int head=0,last=0;
for(int i=1;i<=tot;i++)
if(!du[i]) line[last++]=i;
while(head<last){
int u=line[head++];
for(auto v:E[u])
if(!(--du[v])) line[last++]=v;
}
if(head==tot) printf("Yes\n");
else printf("No\n");
for(int i=1;i<=tot;i++) du[i]=lson[i]=rson[i]=0,E[i].clear();
for(int i=1;i<=n;i++)e[i].clear();
tot=0;
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 45608kb
input:
1 2 1 2 2 1 2 2 1
output:
Yes
result:
wrong answer 1st lines differ - expected: 'No', found: 'Yes'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 2ms
memory: 45896kb
input:
20 250 1 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 3 23 1 24 24 25 25 26 5 26 1 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 7 42 2 43 43 44 44 45 45 46 4 46 2 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 12 55 2 56 56 57 57 58 58 59 59 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
result:
wrong answer 1st lines differ - expected: 'No', found: 'Yes'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Wrong Answer
Test #66:
score: 0
Wrong Answer
time: 23ms
memory: 44976kb
input:
1000 10 1 2 2 3 1 4 4 5 4 6 4 7 2 8 8 9 3 10 2 5 4 1 9 10 1 2 1 3 1 4 4 5 4 6 3 7 3 8 2 9 6 10 2 2 9 1 5 10 1 2 2 3 1 4 4 5 4 6 2 7 3 8 2 9 1 10 2 10 2 7 5 10 1 2 1 3 1 4 2 5 1 6 3 7 2 8 7 9 2 10 2 10 5 2 7 10 1 2 1 3 1 4 3 5 5 6 3 7 7 8 1 9 8 10 2 6 7 1 2 10 1 2 1 3 3 4 2 5 4 6 3 7 1 8 4 9 1 10 2 1...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
wrong answer 24th lines differ - expected: 'No', found: 'Yes'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%