QOJ.ac

QOJ

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

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:52:44]
评测

测评结果：61
用时：281ms
内存：408848kb

查看

[2023-06-24 16:52:41]
提交

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,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 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: 35ms

memory: 381132kb

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

memory: 381236kb

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

memory: 381172kb

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

memory: 381224kb

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

memory: 381176kb

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

memory: 381256kb

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

memory: 381228kb

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

memory: 381232kb

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

memory: 381236kb

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

memory: 381160kb

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

memory: 379180kb

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

memory: 379188kb

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

memory: 381264kb

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

memory: 381188kb

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

memory: 381168kb

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

memory: 379200kb

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

memory: 381260kb

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

memory: 381200kb

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

memory: 381208kb

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

memory: 381164kb

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

memory: 381196kb

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

memory: 381196kb

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

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

memory: 381204kb

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

memory: 381208kb

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

memory: 381216kb

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

memory: 381188kb

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

memory: 381212kb

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

memory: 381180kb

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

memory: 379176kb

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

memory: 381256kb

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

memory: 382680kb

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

memory: 382512kb

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

memory: 382840kb

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

memory: 380252kb

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

memory: 381548kb

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

memory: 399380kb

input:

output:

No

result:

ok single line: 'No'

Test #57:

score: 0

Accepted

time: 93ms

memory: 401020kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #58:

score: 0

Accepted

time: 83ms

memory: 408388kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 0

Accepted

time: 81ms

memory: 408848kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #60:

score: 0

Accepted

time: 64ms

memory: 403768kb

input:

output:

No

result:

ok single line: 'No'

Test #61:

score: 0

Accepted

time: 76ms

memory: 399680kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #62:

score: 0

Accepted

time: 71ms

memory: 405848kb

input:

output:

Yes

result:

ok single line: 'Yes'

Test #63:

score: 0

Accepted

time: 68ms

memory: 405852kb

input:

output:

No

result:

ok single line: 'No'

Test #64:

score: 0

Accepted

time: 240ms

memory: 382312kb

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

memory: 401304kb

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: