oj.uz

Submission #391104

# Submission time Handle Problem Language Result Execution time Memory
391104 2021-04-17T21:01:55 Z saarang123 Usmjeri (COCI17_usmjeri) C++17
140 / 140
 481 ms 85812 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, mxn = 300 * 1000 + 3, lgn = 20;
vector<int> g[mxn];
vector<array<int, 2>> adj[mxn];
int dt[mxn], up[mxn][lgn], cmin[mxn], col[mxn], sub[mxn];
int n, m;

void init(int v, int p = 1) {
	up[v][0] = p;
	for(int i = 1; i < lgn; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for(int u : g[v]) if(u != p) {
		dt[u] = dt[v] + 1;
		init(u, v);
	}
}

int kth(int v, int diff) {
	for(int i = 0; i < lgn; i++)
		if(diff >> i & 1)
			v = up[v][i];
	return v;
}

int lca(int a, int b) {
	if(dt[a] > dt[b]) 
		swap(a, b);
	b = kth(b, dt[b] - dt[a]);
	if(a == b)
		return a;
	for(int i = lgn - 1; i >= 0; i--)
		if(up[a][i] != up[b][i])
			a = up[a][i], b = up[b][i];
	return up[a][0];
}

int connect(int v, int p = -1) {
	sub[v] = cmin[v];
	for(int u : g[v]) if(u != p) {
		sub[v] = min(sub[v], connect(u, v));
		if(sub[u] < dt[v]) {
			adj[u].push_back({v, 0});
			adj[v].push_back({u, 0});
		}
	}
	return sub[v];
}

bool dfs(int v, int c = 0) {
	col[v] = c;
	for(auto &[u, i] : adj[v]) {
		if(col[u] != -1 && (c ^ i) != col[u])
			return false;
		else if(col[u] < 0)
			if(!dfs(u, c ^ i))
				return false;
	}
	return true;
}

long long fexpo(long long a, int b) {
	long long ans = 1;
	while(b > 0) {
		if(b & 1)
			(ans = ans * a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return ans;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    cin >> n >> m;
    memset(col, -1, sizeof col);
    for(int u, v, i = 1; i < n; i++) {
    	cin >> u >> v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    }
    init(1);
    for(int i = 1; i <= n; i++) 
    	cmin[i] = dt[i];
    while(m--) {
    	int u, v;
    	cin >> u >> v;
    	int lc = lca(u, v);
    	cmin[u] = min(cmin[u], dt[lc]);
    	cmin[v] = min(cmin[v], dt[lc]);
    	if(u != lc && v != lc) {
    		adj[u].push_back({v, 1});
    		adj[v].push_back({u, 1});
    	}
    }
    connect(1);
    int cnt = 0;
    for(int i = 2; i <= n; i++) if(col[i] < 0) {
    	if(!dfs(i))
    		return cout << 0 << '\n', 0;
    	cnt++;
    }
    cout << fexpo(2, cnt) << '\n';
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 39692 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 85812 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15692 KB Output is correct
2 Correct 10 ms 15820 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15692 KB Output is correct
2 Correct 10 ms 15784 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16332 KB Output is correct
2 Correct 12 ms 16148 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16332 KB Output is correct
2 Correct 12 ms 16204 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 55564 KB Output is correct
2 Correct 420 ms 57284 KB Output is correct
3 Correct 239 ms 43716 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 59912 KB Output is correct
2 Correct 441 ms 59632 KB Output is correct
3 Correct 316 ms 45984 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 60456 KB Output is correct
2 Correct 407 ms 56628 KB Output is correct
3 Correct 302 ms 46268 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 60768 KB Output is correct
2 Correct 415 ms 61144 KB Output is correct
3 Correct 273 ms 44020 KB Output is correct