답안 #87823 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87823	2018-12-02T17:11:54 Z	jasony123123	Usmjeri (COCI17_usmjeri)	C++11	98 / 140	2000 ms	87180 KB

usmjeri

#define NDEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();


const int MAXN = 300010;
int N, M;

v<int> adjTree[MAXN]; // rooted tree at 0. SZ nodes
int depth[MAXN];
int lowDep[MAXN];

template <int SZ> struct LCA {
	int level[SZ]; // level of node i. node 0 is level 0
	int anc[32][SZ]; // to walk 1<<k up from i. -1 if overflow.
	int maxlvl = 0, maxlg = 0; // only need to consider jumping 2^{0...maxlg} aka maxlvl jmps

	void init(int _n) {
		dfs(0, -1, 0);
		maxlg = 31 - __builtin_clz(maxlvl); // position of last '1'
		FORE(i, 1, maxlg) FOR(j, 0, _n) {
			anc[i][j] = -1;
			if (anc[i - 1][j] != -1)
				anc[i][j] = anc[i - 1][anc[i - 1][j]];
		}
	}

	/* fills level, anc[0], maxlvl */
	void dfs(int cur, int par, int lvl) {
		anc[0][cur] = par, level[cur] = lvl, maxlvl = max(maxlvl, lvl);
		for (auto chi : adjTree[cur]) if (chi != par) dfs(chi, cur, lvl + 1);
	}

	int walk(int a, int k) { // walk "a" k steps
		int e = 31 - __builtin_clz(k); // position of last '1'
		RFORE(i, e, 0)	if (((1 << i)&k) != 0)	a = anc[i][a];
		return a;
	}

	int lca(int a, int b) {
		if (level[a] < level[b]) swap(a, b);
		a = walk(a, level[a] - level[b]);
		if (a == b) return a;
		RFORE(i, maxlg, 0) if (anc[i][a] != anc[i][b]) a = anc[i][a], b = anc[i][b];
		a = anc[0][a], b = anc[0][b];
		assert(a == b);
		return a;
	}
};
LCA<MAXN> lca;

v<int> adjEdges[MAXN];
v<int> badEdges[MAXN];
int comp[MAXN];
int num = 0;

inline void addEdge(int a, int b, v<int> adj[]) {
	adj[a].push_back(b);
	adj[b].push_back(a);
}

void createEdges(int x, int p) {
	for (int c : adjTree[x]) if (c != p) {
		createEdges(c, x);
		lowDep[x] = min(lowDep[x], lowDep[c]);
		if (lowDep[c] < depth[x])
			addEdge(c, x, adjEdges);
	}
}
void makeEdgeTree() {
	FOR(i, 0, M) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		int c = lca.lca(a, b);
		lowDep[a] = min(lowDep[a], depth[c]);
		lowDep[b] = min(lowDep[b], depth[c]);
		if (a != c && b != c) {
			addEdge(a, b, badEdges);
		}
	}
	createEdges(0, -1);
}
void printEdgeTree() {
	FOR(i, 0, N) {
		pf("lowDep[%d] := %d\n", i, lowDep[i]);
	}
}


void dfsDepths(int x, int p, int d) {
	depth[x] = d;
	lowDep[x] = depth[x];
	for (int c : adjTree[x]) if (c != p)
		dfsDepths(c, x, d + 1);
}
void inputTree() {
	cin >> N >> M;
	FOR(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		addEdge(a, b, adjTree);
	}
	dfsDepths(0, -1, 0);
	lca.init(N);
}
void printTree() {
	cout << N << "\n";
	FOR(i, 0, N) {
		pf("depth[%d] := %d\n", i, depth[i]);
		for (int j : adjTree[i])
			cout << i << " -> " << j << "\n";
	}
}

int check(int x, int p, int col) {
	comp[x] = col;
	for (int c : adjEdges[x]) {
		if (comp[c] == 0 && check(c, x, col) == -1)
			return -1;
		else if (comp[c] != comp[x])
			return -1;
	}
	for (int c : badEdges[x]) {
		if (comp[c] == 0 && check(c, x, -col) == -1)
			return -1;
		else if (comp[c] == comp[x])
			return -1;
	}
	return 1;
}

int main() {
	io();
	inputTree();
//	printTree();
	makeEdgeTree();
//	printEdgeTree();

	ll ans = 1;
	FOR(i, 1, N) if (comp[i] == 0) {
		int res = check(i, -1, ++num);
		if (res == -1) {
			cout << "0\n";
			return 0;
		}
		ans <<= 1;
		ans %= 1000000007LL;
	}
	cout << ans << "\n";
	return 0;
}


void io() {
#ifdef LOCAL_PROJECT
	freopen("input.in", "r", stdin);
	freopen("output.out","w",stdout);
#else
	// add i/o method of specific testing system
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	147 ms	43388 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	87180 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	87180 KB	Output is correct
2	Correct	26 ms	87180 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	87180 KB	Output is correct
2	Correct	27 ms	87180 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	87180 KB	Output is correct
2	Correct	28 ms	87180 KB	Output is correct

Subtask #6
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	87180 KB	Output is correct
2	Correct	28 ms	87180 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	459 ms	87180 KB	Output is correct
2	Correct	564 ms	87180 KB	Output is correct
3	Execution timed out	2011 ms	87180 KB	Time limit exceeded

Subtask #8
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	531 ms	87180 KB	Output is correct
2	Correct	495 ms	87180 KB	Output is correct
3	Execution timed out	2053 ms	87180 KB	Time limit exceeded

Subtask #9
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	507 ms	87180 KB	Output is correct
2	Correct	462 ms	87180 KB	Output is correct
3	Correct	350 ms	87180 KB	Output is correct

Subtask #10
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	543 ms	87180 KB	Output is correct
2	Correct	500 ms	87180 KB	Output is correct
3	Execution timed out	2071 ms	87180 KB	Time limit exceeded

답안 #87823

Compilation message