QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#115114	#3501. Jail	st20230851	61	271ms	412424kb	C++14	3.5kb	2023-06-24 16:58:44	2023-06-24 16:58:46

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:58:46]
评测

测评结果：61
用时：271ms
内存：412424kb

查看

[2023-06-24 16:58:44]
提交

answer

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

  int ls[N<<1],rs[N<<1],id=1;
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 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; 
  	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;
}
signed main() {
	ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>Q; 
  while(Q--) {
    cin>>n; prework();
    rep(i,2,n) {
      int u, v;
      cin>>u>>v;
      t[u].push_back(v), t[v].push_back(u);
    }
    dfs1(1), dfs2(1,1);
    builds(rt1,1,n);
    buildt(rt2,1,n);
    cnt=id;
    cin>>m;
    rep(i,1,m) {
      int s, t; ++cnt;
      cin>>s>>t;
      add(id2[dfn[t]],cnt);
      add(cnt,id1[dfn[s]]);
      add(cnt,id2[dfn[s]]);
      add(id1[dfn[t]],cnt);
      work(s,t,cnt);
    }
    puts(topo()?"Yes":"No");
  }
  return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Time Limit Exceeded

Test #1:

score: 5

Accepted

time: 23ms

memory: 379864kb

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

memory: 382312kb

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

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

memory: 382336kb

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

memory: 381152kb

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

memory: 381904kb

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

memory: 381708kb

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

memory: 382504kb

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

memory: 380992kb

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

memory: 382408kb

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

memory: 381776kb

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

memory: 382120kb

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

memory: 382152kb

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

memory: 380916kb

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

memory: 382868kb

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

memory: 382692kb

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

memory: 381160kb

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

memory: 382172kb

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

memory: 382736kb

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

memory: 382132kb

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

memory: 382224kb

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

memory: 381268kb

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

memory: 381704kb

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

memory: 381072kb

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

memory: 382208kb

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

memory: 381552kb

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

memory: 382724kb

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

memory: 381680kb

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

memory: 380992kb

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

memory: 382120kb

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

memory: 382624kb

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

memory: 384132kb

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

memory: 382940kb

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

memory: 384196kb

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

memory: 384072kb

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

memory: 381964kb

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

memory: 402960kb

input:

output:

No

result:

ok single line: 'No'

Test #57:

score: 0

Accepted

time: 99ms

memory: 402892kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #58:

score: 0

Accepted

time: 62ms

memory: 412424kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 0

Accepted

time: 83ms

memory: 410364kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #60:

score: 0

Accepted

time: 76ms

memory: 403228kb

input:

output:

No

result:

ok single line: 'No'

Test #61:

score: 0

Accepted

time: 62ms

memory: 405316kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #62:

score: 0

Accepted

time: 71ms

memory: 403308kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #63:

score: 0

Accepted

time: 68ms

memory: 405380kb

input:

output:

No

result:

ok single line: 'No'

Test #64:

score: 0

Accepted

time: 245ms

memory: 383868kb

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

memory: 404992kb

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: