oj.uz

Submission #380558

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

using namespace std;

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

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

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

	for(auto& [v, idx] : adj[node]){
		if(idx == edgeIdx) continue;
		if(!tin[v]) 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) == (comp[edges[id][0]] == node)) ans[id] = -1;
		else ans[id] = 1;
	}
}

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

	adj.resize(n), bridge_tree.resize(n), edges.resize(m); 
	for(int i = 0; i < m; i++){
		auto& [u, v] = edges[i];
		cin >> u >> v;
		--u, --v;
		if(u == v) continue;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}

	tin.resize(n, 0), comp.resize(n, -1), low.resize(n, 1000000000);
	for(int i = 0; i < n; i++){
		if(tin[i]) continue;
		tarjan(i);
	}

	ans.resize(m, 0), dir.resize(n, 0);
	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]) dfs(i);

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

	return 0; 
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -