답안 #87697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
87697 2018-12-02T04:59:09 Z jasony123123 Usmjeri (COCI17_usmjeri) C++11
0 / 140
5 ms 1184 KB
#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();
int __builtin_clz(int x) { // #0s at beginning
	RFORE(i, 31, 0)
		if (((1 << i)&x) != 0) {
			return 31 - i;
		}
	return 32;
}

const int MAXN = 310;
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<pii> badEdges;
int comp[MAXN];
int num = 0;

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

void colorEdges(int x, int p, int col) {
	comp[x] = col;
	for (int c : adjEdges[x]) if (c != p)
		colorEdges(c, x, col);
}
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) {
			badEdges.push_back({ a,b });
		}
	}
	createEdges(0, -1);
	FOR(i, 1, N) if (comp[i] == 0)
		colorEdges(i, -1, ++num);
}
void printEdgeTree() {
	FOR(i, 0, N) {
		pf("lowDep[%d] := %d\n", i, lowDep[i]);
	}
	for (pii b : badEdges)
		cout << b.first << " must be diff from " << b.second << "\n";
}
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 main() {
	io();
	inputTree();
	//printTree();
	makeEdgeTree();
	//printEdgeTree();
	for (pii opp : badEdges)
		if (comp[opp.first] == comp[opp.second]) {
			cout << 0 << "\n";
			return 0;
		}
			
	ll ans = 1;
	FOR(i, 0, num) {
		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);
}

Compilation message

usmjeri.cpp: In function 'int __builtin_clz(int)':
usmjeri.cpp:23:5: warning: new declaration 'int __builtin_clz(int)' ambiguates built-in declaration 'int __builtin_clz(unsigned int)' [-Wbuiltin-declaration-mismatch]
 int __builtin_clz(int x) { // #0s at beginning
     ^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -