oj.uz

Submission #336079

# Submission time Handle Problem Language Result Execution time Memory
336079 2020-12-14T16:40:48 Z ArminAzimi1 Usmjeri (COCI17_usmjeri) C++14
140 / 140
 1395 ms 148076 KB 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define O_set tree<int, null_type, greater<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
 
const int MAXN = 300000 + 20, MAXM = 5000 + 20, MOD = 1000 * 1000 * 1000 + 7;
const long long INF = 1e9 + 10;
int par[MAXN][30], d[MAXN], x[MAXN], ans[MAXN], par2[MAXN], valpar[MAXN];
vector <pair <int, int> > vec[MAXN];
map <pair <int, int>, int> m;
map <int, int> vis;
bool zer = 0;

void dfs(int u, int par1) {
	par[u][0] = par1;
	for (int i = 0; i < vec[u].size(); i++) {
		int v = vec[u][i].first;
		if (v != par1) {
			d[v] = d[u] + 1;
			dfs(v, u);
		}
	}
}

pair <int, int> parent(int u) {
	vector <pair <int, int>> path;
	path.push_back(make_pair(u, 0));
	int x1 = 0;
	while (par2[u] != u) {
		x1 += valpar[u];
		u = par2[u];
		path.push_back(make_pair(u, x1));
	}
	
	for (int i = 0; i < path.size() - 1; i++) {
		int v = path[i].first;
		int val = path[i].second;
		
		par2[v] = u;
		valpar[v] = (x1 - val) % 2;
	}
	
	return make_pair(u, x1);
}

void dsu(int u, int v, int x) {	
	pair <int, int> d = parent(u);
	int par1 = d.first;
	int val1 = d.second;
	
	d = parent(v);
	
	int par11 = d.first;
	int val11 = d.second;
	
	if (par1 == par11) {
		if ((val1 + val11 + x) % 2 == 1)
			zer = 1;
	}
	else {
		par2[par1] = par11;
		if ((val1 + val11) % 2 == x)
			valpar[par1] = 0;
		else
			valpar[par1] = 1;
	}
}

void dfs1(int u, int par1) {
	for (int i = 0; i < vec[u].size(); i++) {
		int v = vec[u][i].first;
		int ind = vec[u][i].second;
		if (v != par1) {
			dfs1(v, u);
			if (x[v] > 0) {
				dsu(m[make_pair(u, par1)], m[make_pair(v, u)], 0);
			}
			x[u] += x[v];	
		}
	}
	
}


int lca(int a, int b) {
	if (d[a] < d[b]) 
		swap(a, b);
	
	if (d[a] != d[b]) {
		int dis = d[a] - d[b] - 1; 
		int ghabl = a;
		for (int i = 0; i < 22; i++) {
			if ((1 << i) & dis) {
				ghabl = a;
				a = par[a][i];
			}
		}
		
		if (par[a][0] == b) {
			x[a]--;
			x[par[a][0]]--;
			return a;
		}
		a = par[a][0];
		for (int i = 21; i >= 0; i--) {
			if (par[a][i] != par[b][i]) {
				a = par[a][i];
				b = par[b][i];
			}
		}	
	}
	else {
		for (int i = 21; i >= 0; i--) {
			if (par[a][i] != par[b][i]) {
				a = par[a][i];
				b = par[b][i];
			}
		}	
	}
	
	int par1 = par[a][0];
	int yal = m[make_pair(a, par1)];
	int yal1 = m[make_pair(b, par1)];
	dsu(yal, yal1, 1);
	x[a]--;
	x[b]--;
	return par[a][0];
}

void solve() {
	int n, q;
	cin >> n >> q;
	
	
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		cin >> u >> v;
		
		vec[u].push_back(make_pair(v, i));
		vec[v].push_back(make_pair(u, i));
		
		m[make_pair(u, v)] = i;
		m[make_pair(v, u)] = i;
	}
	for (int i = 1; i <= n - 1; i++)	
		par2[i] = i;
	
	dfs(1, 0);
	
	for (int j = 1; j < 22; j++) {
		for (int i = 1; i <= n; i++) {
			if (par[i][j - 1] != -1)
				par[i][j] = par[par[i][j - 1]][j - 1];
			else
				par[i][j] = -1;
		}
	}
	
	while (q--) {
		int a, b;
		cin >> a >> b;
		
		int par1 = lca(a, b);
		x[a]++;
		x[b]++;
	}
	
//	for (int i = 1; i <= n; i++)
//		cout << x[i] << " ";
//	cout << endl;

	dfs1(1, 0);
	
	int ans = 0;
	for (int i = 1; i <= n - 1; i++) {
		pair <int, int> d = parent(i);
		int u = d.first;
//		cout << u << " ";
		if (!vis[u]) {
			vis[u] = 1;
			ans++;
		}
	}
	
	long long x1 = 1;
	for (int i = 0; i < ans; i++)
		x1 = x1 * 2 % MOD;
	
	if (zer)
		cout << 0 << endl;
	else
		cout << x1 << endl;
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int q = 1;
//	cin >> q;
	
	while (q--) {
		solve();
	}
}

Compilation message

usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < vec[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
usmjeri.cpp: In function 'std::pair<int, int> parent(int)':
usmjeri.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < path.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs1(int, int)':
usmjeri.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < vec[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
usmjeri.cpp:74:7: warning: unused variable 'ind' [-Wunused-variable]
   74 |   int ind = vec[u][i].second;
      |       ^~~
usmjeri.cpp: In function 'int lca(int, int)':
usmjeri.cpp:93:7: warning: variable 'ghabl' set but not used [-Wunused-but-set-variable]
   93 |   int ghabl = a;
      |       ^~~~~
usmjeri.cpp: In function 'void solve()':
usmjeri.cpp:165:7: warning: unused variable 'par1' [-Wunused-variable]
  165 |   int par1 = lca(a, b);
      |       ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 53312 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 148076 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7788 KB Output is correct
2 Correct 8 ms 8044 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7788 KB Output is correct
2 Correct 8 ms 8044 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8940 KB Output is correct
2 Correct 16 ms 9068 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8940 KB Output is correct
2 Correct 14 ms 9068 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 108524 KB Output is correct
2 Correct 1173 ms 106704 KB Output is correct
3 Correct 783 ms 73964 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1395 ms 108492 KB Output is correct
2 Correct 1294 ms 108780 KB Output is correct
3 Correct 842 ms 73708 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1387 ms 109276 KB Output is correct
2 Correct 1159 ms 107500 KB Output is correct
3 Correct 875 ms 74020 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1318 ms 109920 KB Output is correct
2 Correct 1239 ms 110188 KB Output is correct
3 Correct 927 ms 70124 KB Output is correct