Submission #331815

#	Time	Username	Problem	Language	Result	Execution time	Memory
331815		ttnhuy313	Usmjeri (COCI17_usmjeri)	C++14	42 / 140	2103 ms	118124 KiB

usmjeri

#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 (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:107:7: warning: unused variable 'uv' [-Wunused-variable]
  107 |   int uv = lca(u, v, d);
      |       ^~

• 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: 14 / 14
• Subtask 10: 0 / 14