QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#377271	#3501. Jail	szzjz	61	1024ms	23852kb	C++14	2.0kb	2024-04-05 10:38:33	2024-04-05 10:38:34

Judging History

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

[2024-04-05 10:38:34]
评测

测评结果：61
用时：1024ms
内存：23852kb

查看

[2024-04-05 10:38:33]
提交

answer

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pub emplace_back
#define pob pop_back
using namespace std;
const int N=120010;
int n,m;
struct E{
	int to,nxt;
}e[N*2];
int head[N],es;
int st[N],ed[N];
int fa[N],top[N],sz[N],dep[N],son[N];
vector<int> to[N];int ins[N];
void add(int x,int y){
	e[++es]={y,head[x]};head[x]=es;
}
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa[x]) continue;
		fa[y]=x;
		dep[y]=dep[x]+1;
		dfs1(y);
		sz[x]+=sz[y];
		if(sz[y]>sz[son[x]]) son[x]=y;
	}
}
void dfs2(int x,int anc){
	top[x]=anc;
	if(son[x]) dfs2(son[x],anc);
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa[x]||y==son[x]) continue;
		dfs2(y,y);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
int dist(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void work(){
	cin>>n;
	es=0;
	for(int i=1;i<=n;i++){
		head[i]=0;
		to[i].clear();
		son[i]=0;
		ins[i]=0;
	}
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>st[i]>>ed[i];
	}
	fa[1]=0;dfs1(1);dfs2(1,1);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j) continue;
			if(dist(st[j],st[i])+dist(st[i],ed[j])==dist(st[j],ed[j])){
				to[i].pub(j);ins[j]++;
			}
			if(dist(st[j],ed[i])+dist(ed[i],ed[j])==dist(st[j],ed[j])){
				to[j].pub(i);ins[i]++;
			}
		}
	}
	queue<int> q;
	for(int i=1;i<=m;i++){
		if(ins[i]==0) q.push(i);
	}
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int y:to[x]){
			ins[y]--;
			if(ins[y]==0) q.push(y);
		}
	}
	for(int i=1;i<=m;i++){
		if(ins[i]){
			cout<<"No"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
}
int main(){
	//freopen("dd.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int tt;cin>>tt;
	while(tt--) work();
	return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Time Limit Exceeded

Test #1:

score: 5

Accepted

time: 0ms

memory: 10520kb

input:

output:

No

result:

ok single line: 'No'

Test #2:

score: 0

Accepted

time: 3ms

memory: 11940kb

input:

output:

No
Yes
Yes
No
Yes
No
Yes
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
Ye...

result:

ok 462 lines

Test #3:

score: 0

Accepted

time: 9ms

memory: 11760kb

input:

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:

ok 1000 lines

Test #4:

score: 0

Accepted

time: 2ms

memory: 10868kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
Yes

result:

ok 20 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 11840kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #6:

score: 0

Accepted

time: 0ms

memory: 11932kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #7:

score: 0

Accepted

time: 64ms

memory: 12960kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #8:

score: 0

Accepted

time: 15ms

memory: 23852kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #9:

score: 0

Accepted

time: 0ms

memory: 10432kb

input:

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:

ok 1000 lines

Test #10:

score: 0

Accepted

time: 47ms

memory: 10324kb

input:

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:

ok 1000 lines

Test #11:

score: -5

Time Limit Exceeded

input:

output:

result:

Subtask #2:

score: 5

Accepted

Test #21:

score: 5

Accepted

time: 3ms

memory: 11796kb

input:

output:

No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes

result:

ok 20 lines

Test #22:

score: 0

Accepted

time: 2ms

memory: 10388kb

input:

output:

Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #23:

score: 0

Accepted

time: 2ms

memory: 11984kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No

result:

ok 20 lines

Test #24:

score: 0

Accepted

time: 0ms

memory: 11080kb

input:

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #25:

score: 0

Accepted

time: 0ms

memory: 10368kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #26:

score: 0

Accepted

time: 2ms

memory: 11220kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #27:

score: 0

Accepted

time: 2ms

memory: 10272kb

input:

output:

Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #28:

score: 0

Accepted

time: 2ms

memory: 12140kb

input:

output:

Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 17 lines

Test #29:

score: 0

Accepted

time: 2ms

memory: 10656kb

input:

output:

No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #30:

score: 0

Accepted

time: 0ms

memory: 12128kb

input:

output:

No
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes

result:

ok 20 lines

Subtask #3:

score: 16

Accepted

Dependency #2:

100%

Accepted

Test #31:

score: 16

Accepted

time: 2ms

memory: 11320kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #32:

score: 0

Accepted

time: 0ms

memory: 10812kb

input:

output:

Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
No

result:

ok 20 lines

Test #33:

score: 0

Accepted

time: 2ms

memory: 11196kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No

result:

ok 20 lines

Test #34:

score: 0

Accepted

time: 2ms

memory: 11780kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
Yes
Yes
No
No
Yes

result:

ok 20 lines

Test #35:

score: 0

Accepted

time: 2ms

memory: 11984kb

input:

output:

Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes

result:

ok 20 lines

Test #36:

score: 0

Accepted

time: 0ms

memory: 11944kb

input:

output:

No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #37:

score: 0

Accepted

time: 2ms

memory: 11872kb

input:

output:

Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No

result:

ok 20 lines

Test #38:

score: 0

Accepted

time: 0ms

memory: 10608kb

input:

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

result:

ok 20 lines

Test #39:

score: 0

Accepted

time: 0ms

memory: 10416kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #40:

score: 0

Accepted

time: 2ms

memory: 11800kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

result:

ok 20 lines

Test #41:

score: 0

Accepted

time: 0ms

memory: 10056kb

input:

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #42:

score: 0

Accepted

time: 2ms

memory: 10772kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Subtask #4:

score: 28

Accepted

Dependency #3:

100%

Accepted

Test #43:

score: 28

Accepted

time: 12ms

memory: 11816kb

input:

output:

No
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #44:

score: 0

Accepted

time: 6ms

memory: 11860kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #45:

score: 0

Accepted

time: 4ms

memory: 11812kb

input:

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
No
No
No
Yes
No

result:

ok 20 lines

Test #46:

score: 0

Accepted

time: 3ms

memory: 10656kb

input:

output:

No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
Yes
No
Yes
No
No

result:

ok 20 lines

Test #47:

score: 0

Accepted

time: 15ms

memory: 11928kb

input:

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes

result:

ok 20 lines

Test #48:

score: 0

Accepted

time: 7ms

memory: 11888kb

input:

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No

result:

ok 20 lines

Test #49:

score: 0

Accepted

time: 9ms

memory: 10424kb

input:

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

result:

ok 20 lines

Test #50:

score: 0

Accepted

time: 8ms

memory: 10576kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Subtask #5:

score: 12

Accepted

Dependency #4:

100%

Accepted

Test #51:

score: 12

Accepted

time: 584ms

memory: 11352kb

input:

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #52:

score: 0

Accepted

time: 1024ms

memory: 11180kb

input:

output:

Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes

result:

ok 20 lines

Test #53:

score: 0

Accepted

time: 357ms

memory: 12992kb

input:

output:

No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes

result:

ok 20 lines

Test #54:

score: 0

Accepted

time: 16ms

memory: 11976kb

input:

output:

Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
No

result:

ok 20 lines

Test #55:

score: 0

Accepted

time: 435ms

memory: 10868kb

input:

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No

result:

ok 20 lines

Test #56:

score: 0

Accepted

time: 82ms

memory: 12544kb

input:

output:

No

result:

ok single line: 'No'

Test #57:

score: 0

Accepted

time: 87ms

memory: 12544kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #58:

score: 0

Accepted

time: 23ms

memory: 17868kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 0

Accepted

time: 23ms

memory: 17596kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #60:

score: 0

Accepted

time: 46ms

memory: 12952kb

input:

output:

No

result:

ok single line: 'No'

Test #61:

score: 0

Accepted

time: 49ms

memory: 12684kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #62:

score: 0

Accepted

time: 18ms

memory: 14376kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #63:

score: 0

Accepted

time: 15ms

memory: 14204kb

input:

output:

No

result:

ok single line: 'No'

Test #64:

score: 0

Accepted

time: 189ms

memory: 10348kb

input:

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #65:

score: 0

Accepted

time: 142ms

memory: 12728kb

input:

1
120000
9596 32034
82692 85993
30880 60468
22127 89935
44536 51056
29638 71986
57153 103961
11021 66919
65177 96684
4542 48982
10457 21422
10762 52690
76467 105536
31498 46755
48690 82310
13509 118283
15463 106906
7541 66632
74654 103950
58261 68753
15087 48231
31649 96398
69483 90580
36955 85619
2...

output:

Yes

result:

ok single line: 'Yes'

Subtask #6:

score: 0

Time Limit Exceeded

Test #66:

score: 11

Accepted

time: 176ms

memory: 11016kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
...

result:

ok 1000 lines

Test #67:

score: 0

Accepted

time: 97ms

memory: 10932kb

input:

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Y...

result:

ok 1000 lines

Test #68:

score: 0

Accepted

time: 107ms

memory: 10532kb

input:

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:

ok 1000 lines

Test #69:

score: -11

Time Limit Exceeded

input: