QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115141#3501. Jailc202301390 52ms257680kbC++142.8kb2023-06-24 17:29:512023-06-24 17:29:52

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 17:29:52]
  • 评测
  • 测评结果:0
  • 用时:52ms
  • 内存:257680kb
  • [2023-06-24 17:29:51]
  • 提交

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%