oj.uz

Submission #380485

# Submission time Handle Problem Language Result Execution time Memory
380485 2021-03-22T03:52:52 Z wind_reaper One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 492 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 100000;

vector<vector<int>> adj;
vector<int> st;
vector<vector<array<int, 2>>> bridge_tree;

vector<int> tin, low, comp;
int timer = 1;

void tarjan(int node, int par = -1){
	tin[node] = low[node] = timer++;
	st.push_back(node);

	for(int v : adj[node]){
		if(v == par) continue;
		if(tin[v] > 0)
			low[node] = min(low[node], tin[v]);
		else{
			tarjan(v, node);
			low[node] = min(low[node], low[v]);
		}
	}

	if(low[node] == tin[node]){
		int v = -1;
		while(v != node){
			v = st.back();
			st.pop_back();
			comp[v] = node;
		}
	}
}

vector<int> ans, dir;
vector<array<int, 2>> edges;

void dfs(int node){
	tin[node] = -1;
	for(auto& [v, id] : bridge_tree[node]){
		if(tin[v] < 0)
			continue;
		dfs(v);
		dir[node] += dir[v];
		if(dir[v] == 0) continue;
		if(dir[v] < 0)
			ans[id] = (edges[id][0] == v && edges[id][1] == node) ? 1 : -1;
		else ans[id] = (edges[id][0] == node && edges[id][1] == v) ? 1 : -1;
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n, m;
	cin >> n >> m;

	tin.resize(n, 0), ans.resize(m, 0), dir.resize(n, 0), edges.resize(m), comp.resize(n, -1);
	adj.resize(n), bridge_tree.resize(n);
	low.resize(n, 0);
	
	for(auto& [u, v] : edges){
		cin >> u >> v;
		--u, --v;
		if(u == v) continue;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(int i = 0; i < n; i++){
		if(tin[i]) continue;
		tarjan(i);
	}

	for(int i = 0; i < m; i++){
		auto [u, v] = edges[i];
		u = comp[u], v = comp[v];
		if(u == v) continue;
		bridge_tree[u].push_back({v, i});
		bridge_tree[v].push_back({u, i});
	}

	int p;
	cin >> p;

	for(int i = 0; i < p; i++){
		int u, v;
		cin >> u >> v;
		u = comp[u-1], v = comp[v-1];
		++dir[u];
		--dir[v];
	}

	for(int i = 0; i < n; i++) if(tin[i] >= 0) dfs(i);

	for(int i = 0; i < m; i++){
		char c = 'B';
		if(ans[i] < 0) c = 'R';
		if(ans[i] > 0) c = 'L';
		cout << c;
	}

	return 0; 
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -