Submission #1307438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307438		Nonoze	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	71 ms	27336 KiB

oneway

/*
*	Author: Nonoze
*	Created: Friday 02/01/2026
*/
#include <bits/stdc++.h>
using namespace std;

#ifndef DEBUG
	#define dbg(...)
#endif

// #define cout cerr << "OUT: "
#define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x; }
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second); }
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), (v).end())
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define QYES quit("YES")
#define QNO quit("NO")

#define int long long
#define double long double
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=20;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}



int n, k, m, q;
vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> edges;
vector<int> ans, sz;


vector<int> tin, low, component;
vector<bool> visited, is_bridge;
int timer = 0;

void dfs_bridges(int u, int p=-1) {
	visited[u] = 1;
	tin[u] = low[u] = timer++;
	for (auto [v, id] : adj[u]) {
		if (v == p) continue;
		if (visited[v]) {
			cmin(low[u], tin[v]);
		} else {
			dfs_bridges(v, u);
			cmin(low[u], low[v]);
			if (low[v] > tin[u]) {
				is_bridge[id] = true;
			}
		}
	}
}

void dfs_comp(int u, int c) {
	component[u] = c;
	for (auto [v, id] : adj[u]) {
		if (component[v] == -1 && !is_bridge[id]) {
			dfs_comp(v, c);
		}
	}
}

void dfs(int u, int p=-1) {
	visited[u] = 1;
	for (auto [v, id] : adj[u]) if (v!=p) {
		dfs(v, u);
		sz[u] += sz[v];
		if (sz[v]==0) ans[id] = 0;
		else {
			int to = (sz[v]>0 ? u : v);
			if (to==component[edges[id].se]) ans[id] = 1;
			else ans[id] = -1;
		}
	}
}


void solve() {
	read(n, m);
	adj.assign(n, {});
	for (int i=0; i<m; i++) {
		int u, v; read(u, v);
		u--, v--;
		edges.pb({u, v});
		if (u>v) swap(u, v);
		adj[u].pb({v, i}), adj[v].pb({u, i});
	}
	
	tin.assign(n, -1), low.assign(n, -1), visited.assign(n, 0), is_bridge.assign(m, false);
	for (int i=0; i<n; i++) {
		if (!visited[i]) {
			dfs_bridges(i);
		}
	}
	component.assign(n, -1);
	int comp_count=0;
	for (int i=0; i<n; i++) {
		if (component[i] == -1) {
			dfs_comp(i, comp_count++);
		}
	}
	
	vector<vector<pair<int, int>>> new_adj(comp_count);
	for (int u=0; u<n; u++) for (auto [v, id] : adj[u]) {
		if (component[u] != component[v]) {
			new_adj[component[u]].pb({component[v], id});
			assert(is_bridge[id]);
		}
	}
	swap(adj, new_adj), n=comp_count;

	ans.assign(m, 0), sz.resize(n, 0);
	read(k);
	for (int i=0; i<k; i++) {
		int a, b; read(a, b); a--, b--;
		sz[component[a]]++, sz[component[b]]--;
	}
	visited.assign(n, 0);
	for (int i=0; i<n; i++) if (!visited[i]) dfs(i);
	for (auto &u: ans) {
		if (u==0) cout << 'B';
		else if (u==1) cout << 'R';
		else cout << 'L';
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40