oj.uz

답안 #365995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
365995 2021-02-12T17:14:55 Z kostia244 Pipes (CEOI15_pipes) C++17
30 / 100
 3578 ms 65536 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(v, -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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Incorrect 2 ms 2796 KB Wrong number of edges

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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