Submission #652134

#	Time	Username	Problem	Language	Result	Execution time	Memory
652134		ymm	Pipes (CEOI15_pipes)	C++17	40 / 100	2191 ms	56808 KiB

pipes

#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];
vector<pii> A[N];
bool ans[N];
int buf[N];
vector<pii> edges;
int n, m;

void dfs(int v, int p, int h)
{
	height[v] = h;
	anc[v][0] = p;
	Loop (i,0,lg-1)
		anc[v][i+1] = anc[anc[v][i]][i];
	for (auto [u, e] : A[v])
		if (u != p)
			dfs(u, v, h+1);
}

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

int flush(int v, int pe)
{
	int ans = buf[v];
	buf[v] = 0;
	for (auto [u, e] : A[v]) {
		if (e != pe)
			ans += flush(u, e);
	}
	if (pe >= 0)
		::ans[pe] |= ans;
	return ans;
}

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], -1);
			A[v].push_back({u,edges.size()});
			A[u].push_back({v,edges.size()});
			edges.push_back({v, u});
			sz[anc[v][lg-1]] += sz[anc[u][lg-1]];
			dfs(u, v, height[v]+1);
		}
	}
	Loop (i,0,n)
		if (anc[i][lg-1] == i)
			flush(i, -1);
	Loop (i,0,edges.size()) {
		if (!ans[i]) {
			cout << edges[i].first+1 << ' ';
			cout << edges[i].second+1 << '\n';
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10