QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706891#6559. A Tree and Two Edgesucup-team902#TL 1ms8848kbC++172.5kb2024-11-03 13:51:302024-11-03 13:51:31

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 13:51:31]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:8848kb
  • [2024-11-03 13:51:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
#define gc getchar
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}

cs int N=50005;

vector<int> e[N];
int fa[N][20];
int in[N],q,n,out[N];
int dfn,dep[N];
void dfs(int u){
	in[u]=++dfn;
	for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int v:e[u])if(v!=fa[u][0]){
		fa[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v);
	}
}
int Lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=19;~i;i--)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
	if(u==v)return u;
	for(int i=19;~i;i--)if(fa[u][i]!=fa[v][i]){
		u=fa[u][i],v=fa[v][i];
	}
	return fa[u][0];
}

int stk[N],top,qu,qv,ans;
vector<int> ee[N];
vector<int>nd;
void add(int u,int v){
	ee[u].pb(v);
	ee[v].pb(u);
	nd.pb(u);
	nd.pb(v);
}
int vs[N];
void ddfs(int u){
	if(u==qv){
		ans++;return;
	}
	vs[u]=1;
	for(int v:ee[u])if(!vs[v]){
		ddfs(v);
	}
	vs[u]=0;
}

int ff[N];
int find(int x){
	return ff[x]==x?x:ff[x]=find(ff[x]);
}
int main(){
	#ifdef Stargazer
	freopen("1.in","r",stdin);
	#endif
	n=read(),q=read();
	pii x(0,0),y(0,0);
	for(int i=1;i<=n;i++)ff[i]=i;
	for(int i=1;i<=n+1;i++){
		int u=read(),v=read();
		int f1=find(u),f2=find(v);
		if(f1!=f2)
		e[u].pb(v),e[v].pb(u),ff[f1]=f2;
		else{
			if(!x.fi)x.fi=u,x.se=v;
			else if(x.fi&&!y.fi)y.fi=u,y.se=v;
		}
	}
	//cout<<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<'\n';
	dep[1]=1;
	dfs(1);
	
	while(q--){
		qu=read(),qv=read();
		vector<int> c;
		c.pb(qu),c.pb(qv);
		c.pb(x.fi),c.pb(x.se),c.pb(y.fi),c.pb(y.se);
		sort(c.begin(),c.end(),[](int i,int j){return in[i]<in[j];});
		top=0;
		for(int i=0;i<c.size();i++){
			int x=c[i];
			if(top){
				int lca=Lca(x,stk[top]);
				if(in[lca]<in[stk[top]]){
					while(top>1&&in[lca]<in[stk[top-1]])add(stk[top-1],stk[top]),top--;
					add(lca,stk[top--]);
					if(stk[top]!=lca)stk[++top]=lca;
				}
			}
			stk[++top]=x;
		}
		while(top>1)add(stk[top-1],stk[top]),top--;
		add(x.fi,x.se);
		add(y.fi,y.se);
		ans=0;
		ddfs(qu);
		cout<<ans<<'\n';
		for(int x:nd)ee[x].clear();
	}
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 8652kb

input:

4 6
1 2
1 3
1 4
2 3
2 4
1 2
1 3
1 4
2 3
2 4
3 4

output:

3
3
3
3
3
4

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 8848kb

input:

6 4
1 2
1 3
1 6
2 3
3 4
3 5
4 5
1 2
1 3
1 4
1 6

output:

2
2
4
1

result:

ok 4 lines

Test #3:

score: -100
Time Limit Exceeded

input:

50000 50000
11561 23122
14261 28523
24407 48814
17947 35894
14803 29607
19557 39115
12415 24830
9583 19167
18397 36794
439 878
18040 36080
17150 34300
7922 15845
18938 37877
18625 37250
6459 12919
9818 19636
3579 7158
21323 42646
23882 47764
13603 27207
8353 16707
15907 31814
20935 41871
11686 23372...

output:

4
3
3
4
4
3
1
3
4
1
3
4
3
4
3
3
1
3
3
3
4
4
4
3
3
3
4
3
3
3
1
3
3
3
3
4
4
4
4
3
4
3
3
3
4
3
4
4
4
4
3
4
4
4
4
3
3
3
4
4
4
4
4
4
3
4
3
4
1
4
1
1
4
3
3
4
3
3
1
4
3
3
4
4
3
3
4
4
4
3
4
3
4
4
4
4
4
3
4
3
3
3
1
3
4
4
3
4
3
4
3
3
4
1
4
3
3
3
4
4
4
4
3
3
3
3
3
4
4
4
4
3
3
4
3
4
4
3
3
4
4
4
1
3
3
3
3
4
4
3
...

result: