Submission #376545

#	Time	Username	Problem	Language	Result	Execution time	Memory
376545		SavicS	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	537 ms	83948 KiB

usmjeri

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 300005;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m;

vector<int> g[maxn];

int d[maxn];
int low[maxn];
int deda[maxn][20];
void dfs1(int v, int p){
	low[v] = d[v];
	deda[v][0] = p;
	ff(i,1,19)deda[v][i] = deda[deda[v][i - 1]][i - 1];
	for(auto u : g[v]){
		if(u != p){
			d[u] = d[v] + 1;
			dfs1(u, v);
		}
	}
}
int lca(int x, int y){
	if(d[x] < d[y])swap(x, y);
	fb(i,19,0){
		if((d[x] - d[y]) & (1 << i))x = deda[x][i];
	}
	fb(i,19,0){
		if(deda[x][i] != deda[y][i]){
			x = deda[x][i];
			y = deda[y][i];
		}
	}
	return (x == y ? x : deda[x][0]);
}

vector<pii> e[maxn];

void add_edge(int x, int y, int z){
	e[x].pb({y, z});
	e[y].pb({x, z});
}

int mn[maxn];
void dfs2(int v, int p){
	mn[v] = low[v];
	for(auto u : g[v]){
		if(u != p){
			dfs2(u, v);
			if(mn[u] < d[v])add_edge(u, v, 0);
			mn[v] = min(mn[v], mn[u]);
		}
	}
}

bool bip = 0;
int boja[maxn];
bool visited[maxn];
void dfs3(int v, int clr){
	visited[v] = 1; 
	boja[v] = clr;
	for(auto c : e[v]){
		int u = c.fi;
		int w = c.se;
		if(!visited[u]){
			dfs3(u, clr ^ w);
		}
		else{
			if(boja[u] != clr ^ w)bip = 1;
		}
	}
}

int main()
{
   	ios::sync_with_stdio(false);
   	cout.tie(nullptr);
  	cin.tie(nullptr);
	cin >> n >> m;
	ff(i,1,n - 1){
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs1(1, -1);
	ff(i,1,n)low[i] = d[i];
	ff(i,1,m){
		int a, b;
		cin >> a >> b;
		int c = lca(a, b);
		low[a] = min(low[a], d[c]);
		low[b] = min(low[b], d[c]);
		if(c != a && c != b)add_edge(a, b, 1);
	}
	dfs2(1, -1);
	ll rez = 1;
	ff(i,2,n){
		if(!visited[i]){
			dfs3(i, 0);
			if(bip == 1)return cout << 0, 0;
			rez = (rez * 2) % mod;
		}	
	}
	cout << rez << endl;
	return 0;
}
/**



// probati bojenje sahovski ili slicno

**/

Compilation message (stderr)

usmjeri.cpp: In function 'void dfs3(int, int)':
usmjeri.cpp:92:15: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   92 |    if(boja[u] != clr ^ w)bip = 1;
      |       ~~~~~~~~^~~~~~

• 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