Submission #80334

#	Time	Username	Problem	Language	Result	Execution time	Memory
80334		mbvdk	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	629 ms	82124 KiB

usmjeri

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14