QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115131#124. Libraryst20230851Compile Error//C++143.3kb2023-06-24 17:16:142023-06-24 17:16:16

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 17:16:16]
  • Judged
  • [2023-06-24 17:16:14]
  • Submitted

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(){
	rep(i,1,n) dfn[i]=sz[i]=fa[i]=top[i]=d[i]=son[i]=0,t[i].clear();
  rep(i,1,cnt) deg[i]=0, e[i].clear(); 
  tot=0, cnt=0;
  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 add1(int p,int l,int r,int L,int R,int c){
    assert(L);
    if(L>R) return;
    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>R) return;
    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 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]]) {
      add1(rt1,1,n,dfn[top[u]],dfn[u],c);
      add2(rt2,1,n,dfn[top[u]],dfn[u],c);
    }
    add1(rt1,1,n,dfn[v]+1,dfn[u],c);
    add2(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);
      add1(rt1,1,n,dfn[top[u]],dfn[u],c);
      add2(rt2,1,n,dfn[top[u]],dfn[u],c);
    }
    if(dfn[u]<dfn[v]) swap(u,v);
    add1(rt1,1,n,dfn[v],dfn[u],c);
    add2(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;
}

详细

/usr/bin/ld: /tmp/ccaBH53X.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccsncFXW.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccsncFXW.o: in function `main':
implementer.cpp:(.text.startup+0x79): undefined reference to `Solve(int)'
collect2: error: ld returned 1 exit status