QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#115084 | #3501. Jail | st20230851 | 0 | 0ms | 0kb | C++14 | 3.6kb | 2023-06-24 16:11:54 | 2023-06-24 16:11:55 |
Judging History
answer
#include<bits/stdc++.h>
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;
int 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 add1(int p,int l,int r,int L,int R,int c){
assert(L);
if(l==L&&r==R){
add(p,c);
return ;
}
int mid=(l+r)>>1;
if(R<=mid) add1(ls[p],l,mid,L,R,c);
else if(L>mid) add1(rs[p],mid+1,r,L,R,c);
else add1(ls[p],l,mid,L,mid,c),add1(rs[p],mid+1,r,mid+1,R,c);
}
void add2(int p,int l,int r,int L,int R,int c){
if(l==L&&r==R){
add(c,p);
return ;
}
int mid=(l+r)>>1;
if(R<=mid) add2(ls[p],l,mid,L,R,c);
else if(L>mid) add2(rs[p],mid+1,r,L,R,c);
else add2(ls[p],l,mid,L,mid,c),add2(rs[p],mid+1,r,mid+1,R,c);
}
void dfs1(int x){
d[x]=d[fa[x]]+1;
sz[x]=1;
for(int y:t[x]){
if(y==fa[x]) continue;
fa[y]=x;
dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]]||!son[x]) son[x]=y;
}
}
void dfs2(int x,int tp) {
dfn[x]=++tot;
top[x]=tp;
if(!son[x]) return ;
dfs2(son[x],tp);
for(int y:t[x]){
if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
}
}
void work(int x,int y,int c){
if(d[x]<d[y]) swap(x,y);
if(dfn[y]<=dfn[x]&&dfn[x]<dfn[y]+sz[y]){
x=fa[x];
while(top[x]!=top[y]){
add1(rt1,1,n,dfn[top[x]],dfn[x],c);
add2(rt2,1,n,dfn[top[x]],dfn[x],c);
x=fa[top[x]];
}
add1(rt1,1,n,dfn[y]+1,dfn[x],c);
add2(rt2,1,n,dfn[y]+1,dfn[x],c);
}else{
x=fa[x],y=fa[y];
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
add1(rt1,1,n,dfn[top[x]],dfn[x],c);
add2(rt2,1,n,dfn[top[x]],dfn[x],c);
x=fa[top[x]];
}
if(dfn[x]<dfn[y]) swap(x,y);
add1(rt1,1,n,dfn[y],dfn[x],c);
add2(rt2,1,n,dfn[y],dfn[x],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;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>Q;
while(Q--){
cin>>n;
prework();
for(int i=2;i<=n;i++){
int x,y;
cin>>x>>y;
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;
cin>>m;
for(int i=1;i<=m;i++){
int s,t;
cin>>s>>t;
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;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1 2 1 2 2 1 2 2 1
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
20 250 1 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 3 23 1 24 24 25 25 26 5 26 1 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 7 42 2 43 43 44 44 45 45 46 4 46 2 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 12 55 2 56 56 57 57 58 58 59 59 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Time Limit Exceeded
Test #66:
score: 0
Time Limit Exceeded
input:
1000 10 1 2 2 3 1 4 4 5 4 6 4 7 2 8 8 9 3 10 2 5 4 1 9 10 1 2 1 3 1 4 4 5 4 6 3 7 3 8 2 9 6 10 2 2 9 1 5 10 1 2 2 3 1 4 4 5 4 6 2 7 3 8 2 9 1 10 2 10 2 7 5 10 1 2 1 3 1 4 2 5 1 6 3 7 2 8 7 9 2 10 2 10 5 2 7 10 1 2 1 3 1 4 3 5 5 6 3 7 7 8 1 9 8 10 2 6 7 1 2 10 1 2 1 3 3 4 2 5 4 6 3 7 1 8 4 9 1 10 2 1...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%