Submission #331824

#	Time	Username	Problem	Language	Result	Execution time	Memory
331824		ttnhuy313	Usmjeri (COCI17_usmjeri)	C++14	0 / 140	398 ms	108652 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, par[2 * N];
vector <int> adj[N];
bool inGraph[N * 2]; // 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, sz;
	dsu_t() {}
	dsu_t(int _n) {
		this -> n = _n;
		sz.assign(n + 5, 1);
		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;
		sz[x] += sz[y];
	}
};

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]);
		}
	}

	return 0;
}

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