oj.uz

Submission #80334

# Submission time Handle Problem Language Result Execution time Memory
80334 2018-10-20T07:54:29 Z mbvdk Usmjeri (COCI17_usmjeri) C++14
140 / 140
 629 ms 82124 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9+7;
vector<int> g[300005];
vector<pii> g2[300005];
int par[19][300005];
int depth[300005], high[300005];
int a[300005], b[300005];
void dfs1(int u, int p, int d){
	depth[u] = d;
	par[0][u] = p;
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i];
		if(v == p) continue;
		dfs1(v, u, d+1);
	}
}
int LCA(int a, int b){
	if(depth[a] < depth[b]) swap(a, b);
	int diff = depth[a]-depth[b];
	for(int i=18;i>=0;i--){
		if((diff>>i)&1) a = par[i][a];
	}
	if(a == b) return a;
	for(int i=18;i>=0;i--){
		if(par[i][a] != par[i][b]) a = par[i][a], b = par[i][b];
	}
	return par[0][a];
}
void dfs2(int u, int p){
	for(int i=0;i<g[u].size();i++){
		int v = g[u][i];
		if(v == p) continue;
		dfs2(v, u);
		high[u] = min(high[u], high[v]);
		if(high[v] < depth[u]){
			g2[u].emplace_back(pii(v, 0));
			g2[v].emplace_back(pii(u, 0));
		}
	}
}
int color[300005];
bool ok = 1;
void dfs3(int u, int c){
	if(color[u] != -1){
		if(color[u] != c){
			ok = 0;
		}
		return;
	}
	color[u] = c;
	for(int i=0;i<g2[u].size();i++){
		int v = g2[u][i].first;
		int c2 = c;
		if(g2[u][i].second == 1) c2 = 1-c2;
		dfs3(v, c2);
	}
}
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=2;i<=n;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs1(1, 0, 0);
	for(int j=1;j<=18;j++){
		for(int i=1;i<=n;i++) par[j][i] = par[j-1][par[j-1][i]];
	}
	for(int i=1;i<=n;i++){
		high[i] = depth[i];
	}
	for(int i=1;i<=m;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		int c = LCA(a, b);
		if(c != a && c != b){
			g2[a].emplace_back(pii(b, 1));
			g2[b].emplace_back(pii(a, 1));
		}
		high[a] = min(high[a], depth[c]);
		high[b] = min(high[b], depth[c]);
	}
	memset(color, -1, sizeof(color));
	dfs2(1, 0);
	ll ans = 1;
	for(int i=2;i<=n;i++){
		if(color[i] == -1){
			ok = 1;
			dfs3(i, 0);
			if(ok) ans = (ans*2)%mod;
			else ans = 0;
		}
	}
	printf("%lld\n", ans);
}

Compilation message

usmjeri.cpp: In function 'void dfs1(int, int, int)':
usmjeri.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs2(int, int)':
usmjeri.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[u].size();i++){
              ~^~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs3(int, int)':
usmjeri.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[u].size();i++){
              ~^~~~~~~~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:63: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:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
usmjeri.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 40440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 82124 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 82124 KB Output is correct
2 Correct 476 ms 82124 KB Output is correct
3 Correct 282 ms 82124 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 82124 KB Output is correct
2 Correct 532 ms 82124 KB Output is correct
3 Correct 380 ms 82124 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 82124 KB Output is correct
2 Correct 445 ms 82124 KB Output is correct
3 Correct 360 ms 82124 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 82124 KB Output is correct
2 Correct 474 ms 82124 KB Output is correct
3 Correct 267 ms 82124 KB Output is correct