Submission #331815

# Submission time Handle Problem Language Result Execution time Memory
331815 2020-11-30T08:59:52 Z ttnhuy313 Usmjeri (COCI17_usmjeri) C++14
42 / 140
2000 ms 118124 KB
#include <bits/stdc++.h>

/*
	Things need to accomplish : 
	- Finding LCA : done
	- Have time_in, time_out : done
	- Decompose into components of demands from predec to ancestor : done
	- Bipartiting
*/

using namespace std;
#define int long long
typedef pair <int, int> ii;

const int N = 3e5 + 5, MOD = 1e9 + 7, lg = 26;
int n, m, d[N], tin[N], tout[N], P[N][lg], x[N], y[N], dfsTime;
vector <int> adj[N];
bool inGraph[N]; // Create a new graph, with nodes are edges and the compenents, they has edges if both points to the same direction

void prepare(int u, int pre) {
	tin[u] = ++dfsTime;
	if (~pre) d[u] = d[pre] + 1;
	for (int v : adj[u]) {
		if (v == pre) continue;
		P[v][0] = u;
		prepare(v, u);
	}
	tout[u] = ++dfsTime;
}

int lca(int u, int v, ii &tw) {
	bool swapped = false;
	if (d[v] > d[u]) {
		swapped = true;
		swap(u, v);
	}
	for (int i = lg - 1; i >= 0; --i) if ((1 << i) <= d[u] - d[v])
		u = P[u][i];
	if (u == v) return u;
	for (int i = lg - 1; i >= 0; --i) if ((1 << i) <= d[u] && P[u][i] != P[v][i])
		u = P[u][i], v = P[v][i];
	if (swapped) swap(u, v);
	tw.first = u, tw.second = v;
	return P[u][0];
}

struct dsu_t {
	int n;
	vector <int> lab;
	dsu_t() {}
	dsu_t(int _n) {
		this -> n = _n;
		lab.assign(n + 5, -1);
	}
	int root(int x) {
		return lab[x] == -1 ? x : lab[x] = root(lab[x]);
	}
	void merge(int u, int v) {
		int x = root(u), y = root(v);
		if (x == y) return;
		lab[y] = x;
	}
};

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);


	cin >> n >> m;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= m; ++i) {
		cin >> x[i] >> y[i];
	}
	prepare(1, -1);
	for (int i = 1; i < lg; ++i) {
		for (int u = 1; u <= n; ++u) {
			P[u][i] = P[P[u][i - 1]][i - 1];
		}
	}
	dsu_t one = dsu_t(n);
	for (int i = 1; i <= m; ++i) {
		int u = x[i], v = y[i];
		if (tin[u] > tin[v]) swap(u, v);
		if (!(tin[u] < tin[v] && tout[u] > tout[v])) continue;
		u = one.root(u), v = one.root(v);
		while (v != u) {
			one.merge(P[v][0], v);
			v = one.root(P[v][0]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		// cerr << "At " << i << ": " << one.root(i) << endl;
		if (one.root(i) == i) inGraph[i] = 1;
		else inGraph[i] = 0;
	}
	dsu_t two = dsu_t(2 * n);
	for (int i = 1; i <= m; ++i) {
		int u = x[i], v = y[i];
		if (tin[u] > tin[v]) swap(u, v);
		if (tin[u] < tin[v] && tout[u] > tout[v]) continue;
		ii d;
		int uv = lca(u, v, d);
		if (one.root(d.first) == one.root(d.second)) {
			cout << 0 << endl;
			return 0;
		}
		d.first = one.root(d.first), d.second = one.root(d.second);
		two.merge(d.first, n + d.second);
		two.merge(d.first + n, d.second);
		u = one.root(u), v = one.root(v);
		while (u != d.first) {
			int pre = one.root(P[u][0]);
			two.merge(pre, u);
			two.merge(pre + n, u + n);
			u = pre;
		}
		while (v != d.second) {
			int pre = one.root(P[v][0]);
			two.merge(pre, v);
			two.merge(pre + n, v + n);
			v = pre;
		}
	}
	for (int i = 1; i <= n; ++i) if (inGraph[i] && two.root(i) == two.root(i + n)) {
		cout << 0 << endl;
		return 0;
	}
	int res = 1;
	for (int i = 1; i <= 2 * n; ++i) if (inGraph[i > n ? i - n : i] && two.root(i) == i) {
		inGraph[i > n ? i - n : i] = 0;
		res = (res * 2) % MOD;
	}
	cout << res << endl;

	return 0;
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:107:7: warning: unused variable 'uv' [-Wunused-variable]
  107 |   int uv = lca(u, v, d);
      |       ^~
# Verdict Execution time Memory Grader output
1 Correct 126 ms 46848 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 315 ms 118124 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7788 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7788 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9068 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9068 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2103 ms 106352 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 810 ms 106348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 637 ms 106628 KB Output is correct
2 Correct 1294 ms 106732 KB Output is correct
3 Correct 323 ms 73324 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 106988 KB Time limit exceeded
2 Halted 0 ms 0 KB -