QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115084#3501. Jailst202308510 0ms0kbC++143.6kb2023-06-24 16:11:542023-06-24 16:11:55

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 16:11:55]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-06-24 16:11:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+9;
int Q,n,m,deg[N],dfn[N],tot,son[N],sz[N],top[N],fa[N],d[N],rt1,rt2;
int id1[N],id2[N],cnt,ls[N<<1],rs[N<<1],id=1;
vector<int>e[N],t[N];
void add(int x,int y){
	deg[y]++;
	e[x].push_back(y);
}
void prework(){
	memset(dfn,0,sizeof(dfn));
	memset(sz,0,sizeof(sz));
	memset(top,0,sizeof(top));
	memset(fa,0,sizeof(fa));
	memset(d,0,sizeof(d));
	memset(son,0,sizeof(son));
	memset(deg,0,sizeof(deg));
	for(int i=1;i<=n;i++){
	  	t[i].clear();
  	}
  	for(int i=1;i<=cnt;i++){
		e[i].clear(); 
  	}
	tot=cnt=0;
	for(int i=1;i<=id;i++){
		ls[i]=rs[i]=0;
	} 
	rt1=rt2=0;
	for(int i=1;i<=n;i++){
		id1[i]=id2[i]=0;
	} 
	id=1;
}
void builds(int &p,int l,int r){
    p=++id;
    if(l==r){
		id1[l]=p; 
		return ;
	} 
	int mid=(l+r)>>1;
    builds(ls[p],l,mid);
	builds(rs[p],mid+1,r);
    add(ls[p],p);
	add(rs[p],p);
}
void buildt(int &p,int l,int r){
    p=++id;
    if(l==r){
		id2[l]=p; 
		return ;
	} 
	int mid=(l+r)>>1;
    buildt(ls[p],l,mid);
	buildt(rs[p],mid+1,r);
    add(p,ls[p]);
	add(p,rs[p]);
}
void add1(int p,int l,int r,int L,int R,int c){
    assert(L);
    if(l==L&&r==R){	
		add(p,c); 
		return ;
	} 
	int mid=(l+r)>>1;
    if(R<=mid) add1(ls[p],l,mid,L,R,c);
    else if(L>mid) add1(rs[p],mid+1,r,L,R,c);
    else add1(ls[p],l,mid,L,mid,c),add1(rs[p],mid+1,r,mid+1,R,c);
}
void add2(int p,int l,int r,int L,int R,int c){
    if(l==L&&r==R){
		add(c,p); 
		return ;
	} 
	int mid=(l+r)>>1;
    if(R<=mid) add2(ls[p],l,mid,L,R,c);
    else if(L>mid) add2(rs[p],mid+1,r,L,R,c);
    else add2(ls[p],l,mid,L,mid,c),add2(rs[p],mid+1,r,mid+1,R,c);
}
void dfs1(int x){
  	d[x]=d[fa[x]]+1;
	sz[x]=1;
  	for(int y:t[x]){ 
	  	if(y==fa[x]) continue; 
	    fa[y]=x;
		dfs1(y); 
		sz[x]+=sz[y];
	    if(sz[y]>sz[son[x]]||!son[x]) son[x]=y;
  	}
}
void dfs2(int x,int tp) {
  	dfn[x]=++tot;
  	top[x]=tp; 
	if(!son[x]) return ;
	dfs2(son[x],tp);
  	for(int y:t[x]){
  		if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
  	}
}
void work(int x,int y,int c){
  	if(d[x]<d[y]) swap(x,y);
  	if(dfn[y]<=dfn[x]&&dfn[x]<dfn[y]+sz[y]){
	    x=fa[x];
	    while(top[x]!=top[y]){
	      	add1(rt1,1,n,dfn[top[x]],dfn[x],c);
	      	add2(rt2,1,n,dfn[top[x]],dfn[x],c);
	      	x=fa[top[x]];
	    }
    	add1(rt1,1,n,dfn[y]+1,dfn[x],c);
    	add2(rt2,1,n,dfn[y]+1,dfn[x],c);
  	}else{
    	x=fa[x],y=fa[y];
    	while(top[x]!=top[y]){
	      	if(d[top[x]]<d[top[y]]) swap(x,y);
	      	add1(rt1,1,n,dfn[top[x]],dfn[x],c);
	      	add2(rt2,1,n,dfn[top[x]],dfn[x],c);
	      	x=fa[top[x]];
    	}
    	if(dfn[x]<dfn[y]) swap(x,y);
    	add1(rt1,1,n,dfn[y],dfn[x],c);
    	add2(rt2,1,n,dfn[y],dfn[x],c);
  	}
}
bool topo(){//拓扑排序 
  	queue<int>q; 
  	for(int i=1;i<=cnt;i++){
  		if(!deg[i]) q.push(i);
  	}
  	while(!q.empty()){
    	int x=q.front();q.pop();
    	for(int y:e[x]){
			if(!(--deg[y])) q.push(y);
		} 
  	}
  	for(int i=1;i<=cnt;i++){
  		if(deg[i]) return 0;
  	}
  	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>Q;
	while(Q--){
		cin>>n;
		prework();
		for(int i=2;i<=n;i++){
			int x,y;
			cin>>x>>y;
		  	t[x].push_back(y);
			t[y].push_back(x);
		}
		dfs1(1);
		dfs2(1,1);
		builds(rt1,1,n);
		buildt(rt2,1,n);
		cnt=id;
		cin>>m;
		for(int i=1;i<=m;i++){
		  	int s,t;
		  	cin>>s>>t;
			cnt++;
		  	add(id2[dfn[t]],cnt);
		  	add(cnt,id1[dfn[s]]);
		  	add(cnt,id2[dfn[s]]);
		  	add(id1[dfn[t]],cnt);
		  	work(s,t,cnt);
		}
		if(topo())cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

1
2
1 2
2
1 2
2 1

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #21:

score: 0
Time Limit Exceeded

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:


result:


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
Time Limit Exceeded

Test #66:

score: 0
Time Limit Exceeded

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:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%