Submission #87825

#	Time	Username	Problem	Language	Result	Execution time	Memory
87825		jasony123123	Usmjeri (COCI17_usmjeri)	C++11	28 / 140	2062 ms	82464 KiB

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].emplace_back(b);
	adj[b].emplace_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;
		sf("%d%d", &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() {
	sf("%d%d", &N, &M);
	FOR(i, 0, N - 1) {
		int a, b;
		sf("%d%d", &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) {
			pf("%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);
}

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:165:13: warning: unknown conversion type character '\x0a' in format [-Wformat=]
    pf("%0\n");
             ^
usmjeri.cpp: In function 'void makeEdgeTree()':
usmjeri.cpp:93:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sf("%d%d", &a, &b);
     ^
usmjeri.cpp: In function 'void inputTree()':
usmjeri.cpp:118:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  sf("%d%d", &N, &M);
    ^
usmjeri.cpp:121:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sf("%d%d", &a, &b);
     ^

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14