Submission #237939

#	Time	Username	Problem	Language	Result	Execution time	Memory
237939		MrRobot_28	Usmjeri (COCI17_usmjeri)	C++17	140 / 140	964 ms	77796 KiB

usmjeri

#include<bits/stdc++.h>
using namespace std;
const int const1 = 1e9 + 7;
long long power(int a, int b){
	if(b == 0)
	{
		return 1;
	}
	else if(b % 2 == 0){
		long long t=  power(a, b / 2);
		return t * t % const1;
	}
	else
	{
		long long t= power(a, b / 2);
		t = t * t % const1;
		return t * a % const1;
	}
}
vector <int> used;
vector <vector <pair <int, int> > > g;
vector <vector <int> > pred;
vector <int> tin, tout, h, h1;
int timer = 0;
bool pr(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
void dfs(int v, int p = -1)
{
	tin[v] = timer++;
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		if(to != p)
		{
			pred[0][to] = v;
			h[to] = h[v] + 1;
			dfs(to, v);
		}
	}
	tout[v] = timer++;
}
vector <vector <int> > g1;
vector <int> dsu, rang;
vector <pair <int, int> > vec;
int lca(int a, int b)
{
	if(pr(a, b))
	{
		for(int j = pred.size() - 1; j >= 0; j--)
		{
			if(!pr(pred[j][b], a))
			{
				b = pred[j][b];
			}
		}
		return pred[0][b];
	}
	else if(pr(b, a))
	{
		for(int j = pred.size() - 1; j >= 0; j--){
			if(!pr(pred[j][a], b))
			{
				a = pred[j][a];
			}
		}
		return pred[0][a];
	}
	else
	{
		for(int j = pred.size() - 1; j >= 0; j--)
		{
			if(!pr(pred[j][a], b))
			{
				a = pred[j][a];
			}
		}
		for(int j = pred.size() - 1; j >= 0; j--)
		{
			if(!pr(pred[j][b], a))
			{
				b = pred[j][b];
			}
		}
		int v = pred[0][a];
		int ind1 = lower_bound(g[v].begin(), g[v].end(), make_pair(a, 0)) - g[v].begin();
		int ind2 = lower_bound(g[v].begin(), g[v].end(), make_pair(b, 0)) - g[v].begin();
		ind1 = g[v][ind1].second;
		ind2 = g[v][ind2].second;
		vec.push_back({ind1, ind2});
		return pred[0][a];
	}
}
int qwer(int a)
{
	if(a == dsu[a])
	{
		return a;
	}
	else
	{
		return dsu[a] = qwer(dsu[a]);
	}
}
void unite(int a, int b)
{
	a = qwer(a);
	b = qwer(b);
	if(a != b)
	{
		if(rang[a] < rang[b])
		{
			swap(a, b);
		}
		dsu[b] = a;
		if(rang[a] == rang[b])
		{
			rang[a]++;
		}
	}
}
void dfs1(int v, int p = -1, int pind = -1)
{
	for(int i = 0; i < g[v].size(); i++){
		int to = g[v][i].first;
		if(to != p)
		{
			dfs1(to, v, g[v][i].second);
			if(h1[to] < h[v])
			{
				unite(pind, g[v][i].second);
			}
			h1[v] = min(h1[v], h1[to]);
		}
	}
}
void dfs2(int v, int c)
{
	used[v] = c;
	for(int i = 0; i < g1[v].size(); i++)
	{
		int to = g1[v][i];
		if(used[to] == -1)
		{
			dfs2(to, 1 - c);
		}
		else if(used[to] != 1 - c)
		{
			cout << 0;
			exit(0);
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	if(n == 1)
	{
		cout << 2;
		return 0;
	}
	g1.resize(n - 1);
	dsu.resize(n - 1);
	rang.resize(n - 1);
	g.resize(n);
	h.resize(n);
	h1.resize(n, 1e9);
	int t = log2(n) + 1;
	pred.resize(t, vector <int> (n));
	tin.resize(n);
	tout.resize(n);
	for(int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	for(int i = 0; i < n; i++){
		sort(g[i].begin(), g[i].end());
	}
	dfs(0);
	for(int j = 1; j < t; j++)
	{
		for(int i = 0; i < n; i++)
		{
			pred[j][i] = pred[j - 1][pred[j - 1][i]];
		}
	}
	for(int i = 0; i < n - 1; i++){
		dsu[i] = i;
		rang[i] = 1;
	}
	while(m--)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if(a == b)
		{
			continue;
		}
		int v = lca(a, b);
		h1[a] = min(h1[a], h[v]);
		h1[b] = min(h1[b], h[v]);
	}
	dfs1(0);
	for(int i = 0; i < vec.size(); i++)
	{
		int a = vec[i].first;
		int b = vec[i].second; 
		a = qwer(a);
		b = qwer(b);
		g1[a].push_back(b);
		g1[b].push_back(a);
	}
	used.resize(n, -1);
	int cnt = 0;
	for(int i = 0; i < n - 1; i++)
	{
		int v = qwer(i);
		if(used[v] == -1)
		{
			cnt++;
			dfs2(v, 0);
		}
	}
	cout << power(2, cnt);
	return 0;
}

Compilation message (stderr)

usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs1(int, int, int)':
usmjeri.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++){
                 ~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs2(int, int)':
usmjeri.cpp:141:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g1[v].size(); i++)
                 ~~^~~~~~~~~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:215:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++)
                 ~~^~~~~~~~~~~~

• 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