oj.uz

답안 #259337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259337 2020-08-07T15:47:49 Z kshitij_sodani Usmjeri (COCI17_usmjeri) C++14
140 / 140
 741 ms 142840 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
llo n,m;
llo mod=1e9+7;
vector<pair<llo,llo>> adj[300001];
vector<pair<llo,llo>> adj2[300001];
llo par[300001][20];
llo par2[300001];
llo st[300001];
llo endd[300001];
llo lev[300001];

llo co=0;
void dfs(llo no,llo par3=-1,llo levv=0,llo par4=-1){
	par[no][0]=par3;
	lev[no]=levv;
	par2[no]=par4;
	st[no]=co;
	co+=1;
	for(auto j:adj[no]){
		if(j.a==par3){
			continue;
		}
		dfs(j.a,no,levv+1,j.b);
	}
	endd[no]=co-1;
}
llo kk(llo no,llo dd){
	for(llo j=0;j<20;j++){
		if(((1<<j)&dd)){
			no=par[no][j];
		}
	}
	return no;
}
llo tree[310001];
void u(llo i,llo j){
	while(i<310001){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo ss(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
vector<llo> mm[300001];
pair<llo,pair<llo,llo>> lca(llo aa,llo bb){
	llo stt=0;
	
	if(lev[aa]>lev[bb]){
		stt=1;
		swap(aa,bb);
	}
	bb=kk(bb,lev[bb]-lev[aa]);
/*	if(aa==bb){
		while(true){
			continue;
		}
	}*/

	for(llo j=19;j>=0;j--){
		if(par[aa][j]!=par[bb][j]){
			aa=par[aa][j];
			bb=par[bb][j];
		}
	}
/*	if(aa==bb){
		while(true){
			continue;
		}
	}*/
	if(stt==0){
		return {par[aa][0],{aa,bb}};
	}
	else{
		return {par[aa][0],{bb,aa}};
	}
}
void dfs2(llo no,llo par3=-1){

	for(auto j:adj[no]){
		if(j.a!=par3){
			dfs2(j.a,no);
		}
	}
	for(auto j:mm[no]){
		u(j+1,-1);
	}
	for(auto j:adj[no]){
		if(j.a!=par3){
			if((ss(endd[j.a]+1)-ss(st[j.a]))>0){
				adj2[par2[no]].pb({j.b,0});
				adj2[j.b].pb({par2[no],0});
			}
		}
	}
}
llo vis[300001];
llo ok=1;
void dfs3(llo no,llo val=0){
	vis[no]=val+1;
	for(auto j:adj2[no]){
		if(vis[j.a]==0){
			dfs3(j.a,(vis[no]-1)^j.b);
		}
		else{
			if((vis[j.a]-1)!=((vis[no]-1)^j.b)){
				ok=0;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<n-1;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb({bb,i});
		adj[bb].pb({aa,i});
	}
	dfs(0);
/*	if(n>5000){
		return 0;
	}*/
	for(llo j=1;j<20;j++){
		for(llo i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}	
	for(llo i=0;i<m;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		if(aa==bb){
			continue;
		}
		if(st[aa]>st[bb]){
			swap(aa,bb);
		}
		if(st[bb]>=st[aa] and st[bb]<=endd[aa]){
			mm[aa].pb(st[bb]);
			u(st[bb]+1,1);
		}
		else{
			pair<llo,pair<llo,llo>> xx=lca(aa,bb);
			mm[xx.a].pb(st[aa]);
			mm[xx.a].pb(st[bb]);
			adj2[par2[xx.b.a]].pb({par2[xx.b.b],1});
			adj2[par2[xx.b.b]].pb({par2[xx.b.a],1});
			u(st[aa]+1,1);
			u(st[bb]+1,1);
		
		}
	}

	dfs2(0);
	llo ans=1;
	for(llo i=0;i<n-1;i++){
		for(auto j:adj2[i]){
			adj2[j.a].pb({i,j.b});
		}
	}
	for(llo i=0;i<n-1;i++){
		/*for(auto j:adj2[i]){
				cout<<i<<":"<<j.a<<":"<<j.b<<endl;
			}*/
		if(vis[i]==0){
			dfs3(i);
			ans=(ans*2)%mod;
		}
	}
	if(ok==0){
		cout<<0<<endl;
	}
	else{
		cout<<ans<<endl;
	}
	//cout<<lca(5,6).a<<","<<lca(5,3).a<<","<<lca(7,1).a<<endl;
/*	for(int i=0;i<n;i++){
		for(int j=0;j<20;j++){
			cout<<par[i][j]<<",";
		}
		cout<<endl;
	}*/
	//cout<<lca(5,3).a<<endl;
	return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 67448 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 142840 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21888 KB Output is correct
2 Correct 16 ms 22144 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21888 KB Output is correct
2 Correct 18 ms 22272 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 23424 KB Output is correct
2 Correct 18 ms 23040 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23424 KB Output is correct
2 Correct 18 ms 23040 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 532 ms 118968 KB Output is correct
2 Correct 591 ms 125636 KB Output is correct
3 Correct 393 ms 91056 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 741 ms 140348 KB Output is correct
2 Correct 688 ms 138416 KB Output is correct
3 Correct 459 ms 102192 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 708 ms 138920 KB Output is correct
2 Correct 586 ms 122052 KB Output is correct
3 Correct 520 ms 101340 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 708 ms 141144 KB Output is correct
2 Correct 661 ms 137592 KB Output is correct
3 Correct 456 ms 93688 KB Output is correct