oj.uz

Submission #43232

# Submission time Handle Problem Language Result Execution time Memory
43232 2018-03-11T07:02:46 Z Quang Usmjeri (COCI17_usmjeri) C++14
140 / 140
 688 ms 106672 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 300010, LOG = 20;

const int MOD = 1000000007;
inline int add(int u, int v) {u += v; if (u >= MOD) u -= MOD; return u;}
inline int sub(int u, int v) {u -= v; if (u < 0) u += MOD; return u;}
inline int mul(int u, int v) {return (long long)u * v % MOD;};
inline int power(int u, int v) {int res = 1; while (v) {if (v & 1) res = mul(res, u); u = mul(u, u); v >>= 1;} return res;}
inline int inv(int u) {return power(u, MOD - 2);}

int n, m;
vector<int> adj[N];
vector<pair<int, int> > adj2[N];
int lv[N], anc[LOG][N], used[N], dir[N];
int minLv[N];

int lca(int u, int v) {
	if (lv[u] > lv[v]) {
		swap(u, v);
	}
	int h = lv[v] - lv[u];
	for (int i = LOG - 1; i >= 0; i--) {
		if ((h >> i) & 1) {
			v = anc[i][v];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = LOG - 1; i >= 0; i--) {
		if (anc[i][u] != anc[i][v]) {
			u = anc[i][u];
			v = anc[i][v];
		}
	}
	return anc[0][u];
}

void dfsInit(int u, int p) {
	lv[u] = lv[p] + 1;
	minLv[u] = lv[u];
	anc[0][u] = p;
	for (int i = 1; i < LOG; i++) {
		anc[i][u] = anc[i - 1][anc[i - 1][u]];
	}
	for (int v : adj[u]) {
		if (v != p) {
			dfsInit(v, u);
		}
	}
}

void dfsCalc(int u, int p) {
	for (int v : adj[u]) {
		if (v != p) {
			dfsCalc(v, u);
			minLv[u] = min(minLv[u], minLv[v]);
			if (minLv[v] < lv[u]) {
				adj2[u].emplace_back(v, 0);
				adj2[v].emplace_back(u, 0);
			}
		}
	}
}

bool dfsRes(int u, int d) {
	if (used[u]) {
		return dir[u] == d;
	}
	used[u] = 1;
	dir[u] = d;
	for (pair<int, int> v : adj2[u]) {
		if (!dfsRes(v.first, d ^ v.second)) {
			return 0;
		}
	}
	return  1;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfsInit(1, 0);
	while (m--) {
		int u, v;
		scanf("%d %d", &u, &v);
		int w = lca(u, v);
		minLv[u] = min(minLv[u], lv[w]);
		minLv[v] = min(minLv[v], lv[w]);
		if (u != w && v != w) {
			adj2[u].emplace_back(v, 1);
			adj2[v].emplace_back(u, 1);
		}
	}
	dfsCalc(1, 0);
	int res = 1;
	for (int i = 2; i <= n; i++) {
		if (!used[i]) {
			res = mul(res, 2);
			if (!dfsRes(i, 0)) {
				res = 0;
			}
		}
	}
	cout << res << endl;
	return 0;
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:84:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
usmjeri.cpp:87:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
                         ^
usmjeri.cpp:94:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
                         ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 34344 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 71792 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 71792 KB Output is correct
2 Correct 15 ms 71792 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 71792 KB Output is correct
2 Correct 18 ms 71792 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 71792 KB Output is correct
2 Correct 17 ms 71792 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 71792 KB Output is correct
2 Correct 18 ms 71792 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 71792 KB Output is correct
2 Correct 573 ms 71792 KB Output is correct
3 Correct 371 ms 71792 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 71844 KB Output is correct
2 Correct 621 ms 79352 KB Output is correct
3 Correct 420 ms 79352 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 85396 KB Output is correct
2 Correct 526 ms 89224 KB Output is correct
3 Correct 410 ms 89224 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 98372 KB Output is correct
2 Correct 561 ms 106672 KB Output is correct
3 Correct 390 ms 106672 KB Output is correct