oj.uz

Submission #380484

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

using namespace std;

const int MXN = 100000;

vector<int> adj[MXN], st;

vector<array<int, 2>> bridge_tree[MXN];

int tin[MXN], low[MXN], comp[MXN], 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;
		}
	}
}

int ans[MXN], dir[MXN];
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;

	edges.resize(m);

	for(auto& [u, v] : edges){
		cin >> u >> v;
		--u, --v;
		if(u == v) continue;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	memset(comp, -1, sizeof comp);
	memset(ans, 0, sizeof ans);
	memset(dir, 0, sizeof dir);

	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 5 ms 6252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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