oj.uz

답안 #331818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
331818 2020-11-30T09:28:24 Z ttnhuy313 Usmjeri (COCI17_usmjeri) C++14
0 / 140
 2000 ms 200812 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) if (x[i] != y[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 = two.root(u);
		}
		while (v != d.second) {
			int pre = one.root(P[v][0]);
			two.merge(pre, v);
			two.merge(pre + n, v + n);
			v = two.root(v);
		}
	}
	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) {
		if (i == 1 || i == n + 1) continue;
		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:106:7: warning: unused variable 'uv' [-Wunused-variable]
  106 |   int uv = lca(u, v, d);
      |       ^~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 43776 KB Output isn't correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 317 ms 111340 KB Output isn't correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2093 ms 7788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 7788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2029 ms 9068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2054 ms 9068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 493 ms 199768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2104 ms 99180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 500 ms 200812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 99564 KB Time limit exceeded
2 Halted 0 ms 0 KB -