QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#377270	#3501. Jail	szzjz	61	1044ms	24040kb	C++14	2.0kb	2024-04-05 10:36:46	2024-04-05 10:36:46

Judging History

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

[2024-04-05 10:36:46]
评测

测评结果：61
用时：1044ms
内存：24040kb

查看

[2024-04-05 10:36:46]
提交

answer

#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: 2ms

memory: 12008kb

input:

output:

No

result:

ok single line: 'No'

Test #2:

score: 0

Accepted

time: 3ms

memory: 11736kb

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: 12020kb

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: 0ms

memory: 12120kb

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: 2ms

memory: 10500kb

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: 4ms

memory: 10812kb

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: 65ms

memory: 13144kb

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: 19ms

memory: 24040kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #9:

score: 0

Accepted

time: 6ms

memory: 11692kb

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: 38ms

memory: 10424kb

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: 10548kb

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: 0ms

memory: 10520kb

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: 11516kb

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: 11408kb

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: 2ms

memory: 11240kb

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: 10980kb

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: 11224kb

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: 11688kb

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: 10764kb

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: 10920kb

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: 10568kb

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: 2ms

memory: 10056kb

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: 0ms

memory: 12028kb

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: 12028kb

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: 11248kb

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: 10204kb

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: 10948kb

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: 2ms

memory: 11116kb

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: 2ms

memory: 10444kb

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: 0ms

memory: 10516kb

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: 2ms

memory: 10636kb

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: 11732kb

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: 11ms

memory: 10948kb

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: 11788kb

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: 0ms

memory: 11116kb

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: 0ms

memory: 10596kb

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: 10428kb

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: 4ms

memory: 12096kb

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: 11800kb

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: 4ms

memory: 11896kb

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: 596ms

memory: 11388kb

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: 1044ms

memory: 12016kb

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: 373ms

memory: 12020kb

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: 12ms

memory: 12216kb

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: 450ms

memory: 12100kb

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: 83ms

memory: 12624kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #58:

score: 0

Accepted

time: 16ms

memory: 17808kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 0

Accepted

time: 23ms

memory: 17820kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #60:

score: 0

Accepted

time: 51ms

memory: 12712kb

input:

output:

No

result:

ok single line: 'No'

Test #61:

score: 0

Accepted

time: 43ms

memory: 12756kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #62:

score: 0

Accepted

time: 15ms

memory: 14256kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #63:

score: 0

Accepted

time: 18ms

memory: 14244kb

input:

output:

No

result:

ok single line: 'No'

Test #64:

score: 0

Accepted

time: 199ms

memory: 10236kb

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: 138ms

memory: 12696kb

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: 173ms

memory: 11120kb

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: 93ms

memory: 10088kb

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: 104ms

memory: 10440kb

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: