QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115138#3501. Jailc202301390 23ms45896kbC++143.0kb2023-06-24 17:21:512023-06-24 17:21:53

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:21:53]
  • 评测
  • 测评结果:0
  • 用时:23ms
  • 内存:45896kb
  • [2023-06-24 17:21:51]
  • 提交

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%