QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#115098	#3501. Jail	st20230851	61	317ms	410328kb	C++14	3.6kb	2023-06-24 16:31:07	2023-06-24 16:31:08

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:31:08]
评测

测评结果：61
用时：317ms
内存：410328kb

查看

[2023-06-24 16:31:07]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define eb emplace_back
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,id1[N],id2[N],cnt;
vector<int> e[N],t[N];

int read(){
  	int x=0,w=1; char c=getchar(); 
  	while(!isdigit(c)){if(c=='-') w=-1; c=getchar();}
  	while(isdigit(c)){x=x*10+(c-'0'); c=getchar();}
  	return x*w;
}
void add(int x,int y) {deg[y]++, e[x].eb(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;
}

  int ls[N<<1],rs[N<<1],id=1;
  void init() {
    rep(i,1,id) ls[i]=rs[i]=0; rt1=rt2=0;
    rep(i,1,n) 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 adds(int p,int l,int r,int x,int y,int z) {
    assert(x);
    if(x>y) return;
    if(l==x&&r==y) {add(p,z); return;} int mid=l+r>>1;
    if(y<=mid) adds(ls[p],l,mid,x,y,z);
    else if(x>mid) adds(rs[p],mid+1,r,x,y,z);
    else adds(ls[p],l,mid,x,mid,z) ,adds(rs[p],mid+1,r,mid+1,y,z);
  }
  void addt(int p,int l,int r,int x,int y,int z) {
    if(x>y) return;
    if(l==x&&r==y) {add(z,p); return;} int mid=l+r>>1;
    if(y<=mid) addt(ls[p],l,mid,x,y,z);
    else if(x>mid) addt(rs[p],mid+1,r,x,y,z);
    else addt(ls[p],l,mid,x,mid,z), addt(rs[p],mid+1,r,mid+1,y,z);
  }


void dfs1(int u) {
  d[u]=d[fa[u]]+1, sz[u]=1;
  for(int v:t[u]) if(v!=fa[u]) {
    fa[v]=u, dfs1(v), sz[u]+=sz[v];
    if(sz[v]>sz[son[u]]) son[u]=v;
  }
}
void dfs2(int u,int tp) {
  dfn[u]=++tot;
  top[u]=tp; if(son[u]) dfs2(son[u],tp);
  for(int v:t[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
void work(int u,int v,int c) {
  if(d[u]<d[v]) swap(u,v);
  if(dfn[v]<=dfn[u]&&dfn[u]<dfn[v]+sz[v]) {
    u=fa[u];
    for(;top[u]!=top[v];u=fa[top[u]]) {
      adds(rt1,1,n,dfn[top[u]],dfn[u],c);
      addt(rt2,1,n,dfn[top[u]],dfn[u],c);
    }
    adds(rt1,1,n,dfn[v]+1,dfn[u],c);
    addt(rt2,1,n,dfn[v]+1,dfn[u],c);
  } else {
    u=fa[u], v=fa[v];
    for(;top[u]!=top[v];u=fa[top[u]]) {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      adds(rt1,1,n,dfn[top[u]],dfn[u],c);
      addt(rt2,1,n,dfn[top[u]],dfn[u],c);
    }
    if(dfn[u]<dfn[v]) swap(u,v);
    adds(rt1,1,n,dfn[v],dfn[u],c);
    addt(rt2,1,n,dfn[v],dfn[u],c);
  }
}
bool topo() {
  queue<int>q; 
  rep(i,1,cnt) if(deg[i]==0) q.push(i);
  while(!q.empty()) {
    int u=q.front(); q.pop();
    for(int v:e[u]) if(!--deg[v]) q.push(v);
  }
  rep(i,1,cnt) if(deg[i]) return 0;
  return 1;
}int main(){
	Q=read();
	while(Q--){
		n=read();
		prework();
		for(int i=2;i<=n;i++){
			int x,y;
			x=read(),y=read();
		  	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;
		m=read();
		for(int i=1;i<=m;i++){
		  	int s,t;
		  	s=read(),t=read();
			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;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Time Limit Exceeded

Test #1:

score: 5

Accepted

time: 26ms

memory: 382320kb

input:

output:

No

result:

ok single line: 'No'

Test #2:

score: -5

Time Limit Exceeded

input:

output:

result:

Subtask #2:

score: 5

Accepted

Test #21:

score: 5

Accepted

time: 237ms

memory: 380452kb

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

memory: 383120kb

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

memory: 381996kb

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

memory: 383624kb

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

memory: 383400kb

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

memory: 381968kb

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

memory: 382792kb

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

memory: 383248kb

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

memory: 381540kb

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

memory: 383312kb

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

memory: 382144kb

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

memory: 380452kb

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

memory: 382536kb

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

memory: 383700kb

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

memory: 382224kb

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

memory: 383548kb

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

memory: 381996kb

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

memory: 382404kb

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

memory: 383060kb

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

memory: 381408kb

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

memory: 382984kb

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

memory: 379916kb

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

memory: 381864kb

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

memory: 383088kb

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

memory: 382552kb

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

memory: 382092kb

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

memory: 382656kb

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

memory: 382760kb

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

memory: 381964kb

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

memory: 382816kb

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

memory: 401968kb

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

memory: 401772kb

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

memory: 401952kb

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

memory: 400992kb

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

memory: 386132kb

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

memory: 402972kb

input:

output:

No

result:

ok single line: 'No'

Test #57:

score: 0

Accepted

time: 51ms

memory: 400788kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #58:

score: 0

Accepted

time: 59ms

memory: 410316kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 0

Accepted

time: 56ms

memory: 410328kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #60:

score: 0

Accepted

time: 76ms

memory: 401136kb

input:

output:

No

result:

ok single line: 'No'

Test #61:

score: 0

Accepted

time: 60ms

memory: 403236kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #62:

score: 0

Accepted

time: 59ms

memory: 405292kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #63:

score: 0

Accepted

time: 70ms

memory: 401200kb

input:

output:

No

result:

ok single line: 'No'

Test #64:

score: 0

Accepted

time: 231ms

memory: 386808kb

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

memory: 404868kb

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

Time Limit Exceeded

input: