oj.uz

Submission #652141

# Submission time Handle Problem Language Result Execution time Memory
652141 2022-10-21T12:47:09 Z ymm Pipes (CEOI15_pipes) C++17
100 / 100
 2316 ms 12700 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100010;
const int lg = 18;

int sz[N];
int anc[N][lg];
int height[N];
struct edge_node {
	int v, e;
	int nxt;
} pool[2*N];
int A[N];

int new_edge_node(int v, int e, int a)
{
	static int nxt = 1;
	pool[nxt].v = v;
	pool[nxt].e = e;
	pool[nxt].nxt = a;
	return nxt++;
}

bool ans[N];
int buf[N];
vector<pii> edges;
int nd[N];
int n, m;

__attribute__((optimize("O0")))
void dfs(int v)
{
	height[v] = anc[v][0] >= 0? height[anc[v][0]]+1: 0;
	Loop (i,0,lg-1)
		anc[v][i+1] = anc[anc[v][i]][i];
	nd[v] = A[v];
	while (nd[v]) {
		if (pool[nd[v]].v != anc[v][0]) {
			anc[pool[nd[v]].v][0] = v;
			dfs(pool[nd[v]].v);
		}
		nd[v] = pool[nd[v]].nxt;
	}
}

int lca(int v, int u)
{
	if (height[v] < height[u])
		swap(v, u);
	int dif = height[v] - height[u];
	Loop (i,0,lg) {
		if (dif & (1<<i))
			v = anc[v][i];
	}
	if (v == u)
		return v;
	LoopR (i,0,lg) {
		if (anc[v][i] != anc[u][i]) {
			v = anc[v][i];
			u = anc[u][i];
		}
	}
	return anc[v][0];
}

__attribute__((optimize("O0")))
int flush(int v)
{
	nd[v] = A[v];
	while (nd[v]) {
		if (pool[nd[v]].v != anc[v][0]) {
			auto tmp = flush(pool[nd[v]].v);
			::ans[pool[nd[v]].e] |= tmp;
			buf[v] += tmp;
		}
		nd[v] = pool[nd[v]].nxt;
	}
	auto tmp = buf[v];
	buf[v] = 0;
	return tmp;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,n) {
		Loop (j,0,lg)
			anc[i][j] = i;
		sz[i] = 1;
	}
	Loop (i,0,m) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		if (anc[v][lg-1] == anc[u][lg-1]) {
			buf[v] += 1;
			buf[u] += 1;
			buf[lca(v, u)] -= 2;
		} else {
			if (sz[anc[v][lg-1]] < sz[anc[u][lg-1]])
				swap(v, u);
			flush(anc[u][lg-1]);
			A[v] = new_edge_node(u, edges.size(), A[v]);
			A[u] = new_edge_node(v, edges.size(), A[u]);
			edges.push_back({v, u});
			sz[anc[v][lg-1]] += sz[anc[u][lg-1]];
			anc[u][0] = v; dfs(u);
		}
	}
	Loop (i,0,n)
		if (anc[i][lg-1] == i)
			flush(i);
	Loop (i,0,edges.size()) {
		if (!ans[i]) {
			cout << edges[i].first+1 << ' ';
			cout << edges[i].second+1 << '\n';
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 6 ms 852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 724 KB Output is correct
2 Correct 131 ms 792 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 1660 KB Output is correct
2 Correct 292 ms 1640 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 3280 KB Output is correct
2 Correct 401 ms 4080 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 9288 KB Output is correct
2 Correct 692 ms 9292 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 10316 KB Output is correct
2 Correct 967 ms 10208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 12548 KB Output is correct
2 Correct 1704 ms 12588 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2019 ms 12528 KB Output is correct
2 Correct 2011 ms 12588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2316 ms 12048 KB Output is correct
2 Correct 2060 ms 12700 KB Output is correct