oj.uz

Submission #142702

# Submission time Handle Problem Language Result Execution time Memory
142702 2019-08-10T14:32:22 Z Anai Pipes (CEOI15_pipes) C++14
40 / 100
 3718 ms 24096 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 6e6 + 5, LG = 18;

vector<int> g[N];
int dsu[N], lvl[N], pos[N], accm[N], rmq[LG][N * 2], lg2[N * 2];

bitset<M> edgs(0);
int n, m, lptr;

static int get_dsu(int nod) {
	return (dsu[nod] ? (dsu[nod] = get_dsu(dsu[nod])) : nod); }

static bool join(int a, int b) {
	a = get_dsu(a);
	b = get_dsu(b);
	if (a == b)
		return false;
	if (rand() % 2)
		swap(a, b);
	dsu[a] = b;
	return true; }

static void dfs(int u, int pap = 0) {
	rmq[0][++lptr] = u;
	lvl[u] = lvl[pap] + 1;
	pos[u] = lptr;
	for (auto v: g[u]) if (v != pap) {
		dfs(v, u);
		rmq[0][++lptr] = u; } }

static void build_rmq() {
	for (int i = 2; i < 2 * N; ++i)
		lg2[i] = 1 + lg2[i / 2]; 

	for (int lg = 1; lg < LG; ++lg)
	for (int i = 1; i <= 2 * (n - 1); ++i) {
		int l = i, r = min(2 * (n - 1), i + (1 << lg - 1));
		rmq[lg][i] = min(make_pair(lvl[rmq[lg - 1][l]], rmq[lg - 1][l]), make_pair(lvl[rmq[lg - 1][r]], rmq[lg - 1][r])).second; } }

static int lca(int a, int b) {
	int l;
	a = pos[a];
	b = pos[b];
	if (a > b)
		swap(a, b);
	l = lg2[b - a];
	return min(make_pair(lvl[rmq[l][a]], rmq[l][a]), make_pair(lvl[rmq[l][b - (1 << l) + 1]], rmq[l][b - (1 << l) + 1])).second; }

static void answer(int nod, int pap = 0) {
	for (auto v: g[nod]) if (v != pap) {
		answer(v, nod);
		accm[nod]+= accm[v]; }
	if (!accm[nod] && pap != 0)
		cout << nod << ' ' << pap << '\n'; }

int main() {
#ifdef HOME
	freopen("pipes.in", "r", stdin);
	freopen("pipes.out", "w", stdout);
#else
	srand(time(NULL));
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int a, b, i = 0; i < m; ++i) {
		cin >> a >> b;
		if (join(a, b)) {
			edgs[i] = true;
			g[a].push_back(b);
			g[b].push_back(a); } }

	rewind(stdin);

	for (int i = 1; i <= n; ++i)
		if (!lvl[i])
			dfs(i);

	build_rmq();

	cin >> n >> m;
	for (int a, b, i = 0; i < m; ++i)  {
		cin >> a >> b;
		if (!edgs[i]) {
			accm[a]+= 1, accm[b]+= 1;
			accm[lca(a, b)]-= 2; } }

	for (int i = 1; i <= n; ++i)
		if (lvl[i] == 1)
			answer(i);

	return 0; }

Compilation message

pipes.cpp: In function 'void build_rmq()':
pipes.cpp:39:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   int l = i, r = min(2 * (n - 1), i + (1 << lg - 1));
                                             ~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3704 KB Output is correct
2 Correct 5 ms 3576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4500 KB Output is correct
2 Correct 12 ms 4472 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 7068 KB Output is correct
2 Correct 255 ms 7072 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 6732 KB Output is correct
2 Correct 532 ms 6776 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 9372 KB Output is correct
2 Runtime error 726 ms 23160 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1198 ms 17264 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1912 ms 20532 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2465 ms 24096 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3219 ms 23472 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3718 ms 21308 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -