oj.uz

답안 #365996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365996 2021-02-12T17:15:56 Z kostia244 Pipes (CEOI15_pipes) C++17
40 / 100
 3338 ms 57056 KB 
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct dsu {
	vector<int> r, p;
	dsu(int n = 0) : r(n, 1), p(n) { iota(all(p), 0); }
	int par(int i) { return p[i] == i ? i : p[i] = par(p[i]); }
	void join(int u, int v) {
		u = par(u), v = par(v);
		if(u == v) return;
		p[v] = u;
		r[u] += r[v];
	}
	bool connected(int u, int v) {
		return par(u) == par(v);
	}
};
const int maxn = 1e5+1, lg = 17;
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[p[v][i-1]][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>>i)&1) v = p[v][i];
	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];
	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.r[ru] < comp.r[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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3308 KB Output is correct
2 Correct 7 ms 3308 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 3308 KB Output is correct
2 Correct 170 ms 3308 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 330 ms 3988 KB Output is correct
2 Correct 373 ms 4076 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 562 ms 5868 KB Output is correct
2 Runtime error 474 ms 20460 KB Memory limit exceeded

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1035 ms 11884 KB Output is correct
2 Runtime error 863 ms 30060 KB Memory limit exceeded

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1526 ms 13292 KB Output is correct
2 Runtime error 1289 ms 46316 KB Memory limit exceeded

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2661 ms 15596 KB Output is correct
2 Runtime error 2685 ms 57056 KB Memory limit exceeded

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2827 ms 21228 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3338 ms 33224 KB Memory limit exceeded
2 Halted 0 ms 0 KB -