oj.uz

Submission #87833

# Submission time Handle Problem Language Result Execution time Memory
87833 2018-12-02T17:29:04 Z jasony123123 Usmjeri (COCI17_usmjeri) C++11
140 / 140
 698 ms 81248 KB 
#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;
const int LOG = 19;

int N, M;

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

namespace LCA {
	int anc[MAXN][LOG];

	void setup(int N) {
		for (int j = 1; j < LOG; j++)
			for (int i = 0; i < N; i++)
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
	}

	int lca(int x, int y) {
		if (depth[x] < depth[y])
			swap(x, y);
		int diff = depth[x] - depth[y];
		for (int i = LOG - 1; i >= 0; i--)
			if (diff >> i & 1)
				x = anc[x][i];
		if (x == y)
			return x;
		for (int i = LOG - 1; i >= 0; i--)
			if (anc[x][i] != anc[y][i]) {
				x = anc[x][i];
				y = anc[y][i];
			}
		return anc[x][0];
	}
}


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) {
	LCA::anc[x][0] = p;
	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::setup(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
	// doesnt work with scanf??
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
}

Compilation message

usmjeri.cpp: In function 'void makeEdgeTree()':
usmjeri.cpp:83: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:109: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:112: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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 42104 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 81248 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 81248 KB Output is correct
2 Correct 27 ms 81248 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 81248 KB Output is correct
2 Correct 26 ms 81248 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 81248 KB Output is correct
2 Correct 31 ms 81248 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 81248 KB Output is correct
2 Correct 29 ms 81248 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 81248 KB Output is correct
2 Correct 617 ms 81248 KB Output is correct
3 Correct 367 ms 81248 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 81248 KB Output is correct
2 Correct 556 ms 81248 KB Output is correct
3 Correct 395 ms 81248 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 81248 KB Output is correct
2 Correct 638 ms 81248 KB Output is correct
3 Correct 454 ms 81248 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 81248 KB Output is correct
2 Correct 613 ms 81248 KB Output is correct
3 Correct 346 ms 81248 KB Output is correct