oj.uz

Submission #366002

# Submission time Handle Problem Language Result Execution time Memory
366002 2021-02-12T17:37:09 Z kostia244 Pipes (CEOI15_pipes) C++17
100 / 100
 3008 ms 14572 KB 
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 1e5+1, lg = 11;
struct dsu {
	int p[maxn];
	dsu(int n = 0) {
		for(int i = 0; i <= n; i++) p[i] = -1;
	}
	int par(int i) { return p[i] < 0 ? i : p[i] = par(p[i]); }
	void join(int u, int v) {
		u = par(u), v = par(v);
		if(u == v) return;
		p[u] += p[v];
		p[v] = u;
	}
	bool connected(int u, int v) {
		return par(u) == par(v);
	}
};
dsu comp;
int n, m;
int h[maxn], eval[maxn], lval[maxn], p[maxn][lg];
array<int, 2> elist[maxn];
vector<array<int, 2>> g[maxn];
void accumulate(int v, int p, int eid) {
	for(auto [i, id] : g[v]) if(i != p) {
		accumulate(i, v, id);
		lval[v] += lval[i];
	}
	if(eid != -1 && lval[v]) {
		eval[eid] += lval[v];
		//cout << elist[eid][0] << " " << elist[eid][1] << " += " << lval[v] << endl;
	}
}
void attach(int v, int pr) {
	lval[v] = 0;
	p[v][0] = pr;
	for(int i = 1; i < lg; i++) {
		p[v][i] = p[v][i-1];
		p[v][i] = p[p[v][i]][i-1];
		p[v][i] = p[p[v][i]][i-1];
	}
	for(auto [i, id] : g[v]) if(i != pr) {
		h[i] = h[v]+1;
		attach(i, v);
	}
}
int ESZ = 0;
int lca(int u, int v) {
	if(h[u] > h[v]) swap(u, v);
	int dif = h[v]-h[u];
	for(int i = 0; i < lg; i++) {
		if(dif%3) v = p[v][i], dif--;
		if(dif%3) v = p[v][i];
		dif /= 3;
	}
	if(u == v) return u;
	for(int i = lg; i--;) {
		if(p[v][i] != p[u][i]) v = p[v][i], u = p[u][i];
		if(p[v][i] != p[u][i]) v = p[v][i], u = p[u][i];
	}
	return p[u][0];
}
void add_edge(int u, int v) {
	if(comp.connected(u, v)) {
		int L = lca(u, v);
		//cout << u << " " << v << " lca = " << L << endl;
		lval[u]++, lval[v]++, lval[L] -= 2;
	} else {
		int ru = comp.par(u), rv = comp.par(v);
		if(-comp.p[ru] < -comp.p[rv]) swap(u, v), swap(ru, rv);
		//cout << u<< " is god " << endl;
		comp.join(ru, rv);
		h[v] = h[u]+1;
		accumulate(rv, -1, -1);
		attach(v, u);
		g[u].push_back({v, ESZ});
		g[v].push_back({u, ESZ});
		elist[ESZ++] = {u, v};
	}
}
void debug(int v, int p = -1) {
	for(auto [i, id] : g[v]) if(i != p) {
		cout << v << " -> " << i << endl;
		debug(i, v);
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	comp = dsu(n+1);
	for(int f, t; m--;) {
		cin >> f >> t;
		add_edge(f, t);
		//cout << m << endl;
		//for(int i = 1; i <= n; i++) if(comp.par(i) == i) {
		//	debug(i);
		//}
	}
	accumulate(comp.par(1), -1, -1);
	for(int i = 0; i < ESZ; i++) if(!eval[i]) cout << elist[i][0] << " " << elist[i][1] << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3692 KB Output is correct
2 Correct 8 ms 3712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 4332 KB Output is correct
2 Correct 169 ms 4600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 4972 KB Output is correct
2 Correct 371 ms 5076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 6532 KB Output is correct
2 Correct 491 ms 7276 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 10476 KB Output is correct
2 Correct 753 ms 10476 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 11508 KB Output is correct
2 Correct 1213 ms 11244 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2116 ms 13420 KB Output is correct
2 Correct 1992 ms 13548 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2538 ms 14572 KB Output is correct
2 Correct 2427 ms 14444 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3008 ms 13036 KB Output is correct
2 Correct 2551 ms 14088 KB Output is correct