oj.uz

답안 #823647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823647 2023-08-12T23:40:22 Z NK_ One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3000 ms 212 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;

struct DSU {
	vi e; void init(int N) { e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) return 0;
		e[x] += e[y]; e[y] = x; return 1;
	}
};
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	DSU D; D.init(N);
	V<V<pi>> adj(N); V<pi> ex, E;
	string ans(M, 'B');
	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		E.pb(mp(u, v));
		if (D.unite(u, v)) adj[u].pb(mp(v, i)), adj[v].pb(mp(u, i));
		else ex.pb(mp(u, v));
	}

	V<pi> par(N); vi dep(N);
	function<void(int)> dfs = [&](int u) {
		for(auto& v : adj[u]) if (v.f != par[u].f) { par[v.f] = mp(u, v.s); dep[v.f] = dep[u] + 1; dfs(v.f); }
	};
	
	par[0] = mp(0, -1); dep[0] = 0; dfs(0);

	D.init(N);
	for(auto& p : ex) {
		auto [u, v] = p;

		while(1) {
			int a = D.get(u), b = D.get(v);
			if (a == b) break;
			if (dep[a] < dep[b]) swap(a, b);
			D.unite(par[a].f, a);
		}
	}

	V<V<pi>> ADJ(N);
	for(int u = 0; u < N; u++) for(auto& v : adj[u]) if (D.get(v.f) != D.get(u)) {
		int a = D.get(u), b = D.get(v.f);
		ADJ[a].pb(mp(b, v.s));
	}

	int R = D.get(0);

	adj.swap(ADJ);

	par[R] = mp(0, -1); dep[R] = 0; dfs(R);

	vi to(M, -1);

	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int u, v; cin >> u >> v; --u, --v;
		if (D.get(u) == D.get(v)) continue;

		// cout << u << " " << v << endl;

		while(1) {
			int a = D.get(u), b = D.get(v);
			// cout << u << " " << v << endl;
			// cout << a << " " << b << endl;
			if (a == b) break;
			if (dep[a] < dep[b]) swap(a, b);
			// cout << D.get(u) << " -> " << a << endl;
			// change label of edge
			to[par[a].s] = (D.get(u) == a ? par[a].f : a);
			D.unite(par[a].f, a);
		}
	}

	for(int i = 0; i < M; i++) if (to[i] != -1) {
		// cout << to[i] << endl;
		ans[i] = (E[i].f == to[i] ? 'L' : 'R');
	}

	cout << ans << nl;

    return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3061 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3061 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3061 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -