oj.uz

Submission #239609

# Submission time Handle Problem Language Result Execution time Memory
239609 2020-06-16T19:22:37 Z NONAME Usmjeri (COCI17_usmjeri) C++14
28 / 140
 500 ms 86096 KB 
#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int N = 3e5 + 10;
const int base = 1e9 + 7;

int n, m, col[N], tin[N], tout[N], depth[N], pr[N], up[N][30], d[N], timer;
bool mk[N];
vector <pair <int, int> > e;
vector <int> g[N];

void paint(int v, int cl) {
	if (mk[v]) {
		if (col[v] != cl) {
			cout << 0;
			exit(0);
		}
		return;
	}
	
	mk[v] = 1;
	col[v] = cl;
	
	for (int to : g[v])
		paint(to, cl ^ 1);
}

void dfs(int v, int pred = 0) {
	tin[v] = timer++;
	
	pr[v] = pred;
	up[v][0] = pred;
	for (int i = 1; i < 20; ++i)
		up[v][i] = up[up[v][i - 1]][i - 1];
	
	for (int to : g[v]) {
		if (to == pred)
			continue;
			
		depth[to] = depth[v] + 1;
			
		dfs(to, v);
	}
	
	tout[v] = timer++;
}

bool upper(int x, int y) { return (tin[x] < tin[y]) && (tout[x] > tout[y]); }

int _lca(int x, int y) {
	if (upper(x, y))
		return x;
	if (upper(y, x))
		return y;
		
	for (int i = 19; i >= 0; --i)
		if (!upper(up[x][i], y))
			x = up[x][i];
	
	return up[x][0];
}

int f(int x) { return (x == d[x]) ? x : d[x] = f(d[x]); }

void find(int v) {
	if (!v)
		return;
		
	if (f(pr[v]) == f(v)) {
		find(pr[v]);
		pr[v] = pr[pr[v]];
	}
}

void path(int v, int u) {
	find(v);
	while (depth[pr[v]] > depth[u]) {
		d[f(v)] = f(pr[v]);
		find(v = pr[v]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(0);
	
	for (int i = 0; i < n; ++i)
		d[i] = i;

	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		
		if (x == y)
			continue;
			
		if (tin[x] > tin[y])
			swap(x, y);
			
		if (tout[x] > tout[y]) path(y, x);
			else {
				int lca = _lca(x, y);
				
				path(x, lca);
				path(y, lca);
				
				e.push_back(make_pair(x, y));
			}
	}
	
	//for (int i = 0; i < n; ++i)
		//cout << f(i) << ' ';
	//cout << '\n';
	
	for (int i = 0; i < n; ++i)
		g[i].clear();
		
	for (auto a : e) {
		int x = f(a.first);
		int y = f(a.second);
		
		if (x == y) {
			cout << 0;
			return 0;
		}
		
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	for (int i = 0; i < n; ++i)
		if (!mk[i])
			paint(i, 0);
	
	for (auto a : e)
		pr[f(a.first)] = f(a.second);
		
	set <int> s;
	s.clear();
	for (int i = 1; i < n; ++i)
		s.insert(f(i));
		
	int ans = 1;
	for (int i = 0; i < int(s.size()); ++i)
		ans = (ans + ans) % base;
	
	cout << ans << '\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 32504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 86096 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 8448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 8456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 73932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 474 ms 76892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 500 ms 77408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 473 ms 77296 KB Output isn't correct
2 Halted 0 ms 0 KB -