oj.uz

Submission #81751

# Submission time Handle Problem Language Result Execution time Memory
81751 2018-10-26T12:18:16 Z farukkastamonuda Usmjeri (COCI17_usmjeri) C++14
140 / 140
 634 ms 76560 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
using namespace std;
int n,m,x,y,baba[22][li],dep[li],h[li],vis[li],say=1;
vector<int> v[li];
vector< pair<int,int> > v2[li];
void dfs(int node,int ata,int der){
	baba[0][node]=ata;
	dep[node]=der;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata) continue;
		dfs(go,node,der+1);
	}
}
void b_lca(){
	for(int i=1;i<=20;i++){
		for(int j=1;j<=n;j++){
			baba[i][j]=baba[i-1][baba[i-1][j]];
		}
	}
}
int f_lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dx=dep[x];
	int dy=dep[y];
	for(int i=20;i>=0;i--){
		if(dx-(1<<i)>=dy){
			dx-=(1<<i);
			x=baba[i][x];
		}
	}
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(baba[i][x]!=baba[i][y]){
			x=baba[i][x];
			y=baba[i][y];
		}
	}
	return baba[0][x];
}
int build(int x){
	for(int i=0;i<(int)v[x].size();i++){
		int go=v[x][i];
		if(go==baba[0][x]) continue;
		int val=build(go);
		h[x]=min(h[x],val);
		if(val<dep[x]){
			v2[x].pb(mp(go,0));
			v2[go].pb(mp(x,0));
		}
	}
	return h[x];
}
int dfs2(int node,int ata,int renk){
	if(vis[node]!=-1) return (vis[node]==renk);
	vis[node]=renk;
	for(int i=0;i<(int)v2[node].size();i++){
		int go=v2[node][i].fi;
		int deg=v2[node][i].se;
		if(go==ata) continue;
		if(dfs2(go,node,renk^deg)==0){
			return 0;
		}
	}
	return 1;
}
int main(){
	memset(vis,-1,sizeof(vis));
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		v[x].pb(y);
		v[y].pb(x);
	}
	dfs(1,-1,0);
	b_lca();
	for(int i=1;i<=n;i++) h[i]=dep[i];
	for(int i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		int lca=f_lca(x,y);
		if(lca!=x && lca!=y){
			v2[x].pb(mp(y,1));
			v2[y].pb(mp(x,1));
		}
		h[x]=min(h[x],dep[lca]);
		h[y]=min(h[y],dep[lca]);
	}
	build(1);
	for(int i=2;i<=n;i++){
		if(vis[i]==-1){
			if(dfs2(i,-1,0)==0){
				printf("0\n");
				return 0;
			}
			say=(say*2ll)%md;
		}
	}
	printf("%d\n",say);
	return 0;
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
usmjeri.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
usmjeri.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 36728 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 76560 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 76560 KB Output is correct
2 Correct 17 ms 76560 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 76560 KB Output is correct
2 Correct 17 ms 76560 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 76560 KB Output is correct
2 Correct 20 ms 76560 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 76560 KB Output is correct
2 Correct 21 ms 76560 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 76560 KB Output is correct
2 Correct 458 ms 76560 KB Output is correct
3 Correct 319 ms 76560 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 76560 KB Output is correct
2 Correct 541 ms 76560 KB Output is correct
3 Correct 356 ms 76560 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 76560 KB Output is correct
2 Correct 443 ms 76560 KB Output is correct
3 Correct 376 ms 76560 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 76560 KB Output is correct
2 Correct 517 ms 76560 KB Output is correct
3 Correct 321 ms 76560 KB Output is correct