QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#115141 | #3501. Jail | c20230139 | 0 | 52ms | 257680kb | C++14 | 2.8kb | 2023-06-24 17:29:51 | 2023-06-24 17:29:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
const int N=5e6+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]],dfn[u],i);
query2(rt2,1,n,dfn[top[u]],dfn[u],i);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
query1(rt1,1,n,dfn[u],dfn[v],i);
query2(rt2,1,n,dfn[u],dfn[v],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: 5
Accepted
time: 35ms
memory: 255920kb
input:
1 2 1 2 2 1 2 2 1
output:
No
result:
ok single line: 'No'
Test #2:
score: -5
Wrong Answer
time: 27ms
memory: 257484kb
input:
462 120 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 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 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
wrong answer 2nd lines differ - expected: 'Yes', found: 'No'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 33ms
memory: 257184kb
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:
No No No No No No No No No No No No No No No No No No No No
result:
wrong answer 7th lines differ - expected: 'Yes', found: 'No'
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: 52ms
memory: 257680kb
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:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
wrong answer 1st lines differ - expected: 'Yes', found: 'No'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%