oj.uz

Submission #43227

# Submission time Handle Problem Language Result Execution time Memory
43227 2018-03-11T05:59:42 Z Quang Usmjeri (COCI17_usmjeri) C++14
28 / 140
 693 ms 102368 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], cnt[N], used[N], dir[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;
	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);
			cnt[u] += cnt[v];
		}
	}
	if (cnt[u]) {
		adj2[u].emplace_back(p, 0);
		adj2[p].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);
		cnt[u]++, cnt[v]++;
		cnt[w] -= 2;
		if (u != w && v != w) {
			adj2[u].emplace_back(v, 1);
			adj2[v].emplace_back(u, 1);
		}
	}
	dfsCalc(1, 0);
	// for (int i = 1; i <= n; i++) {
	// 	cout << cnt[i] << endl;
	// }
	int res = 1;
	for (int i = 1; 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:82: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:85: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:92: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 146 ms 37752 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 82536 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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