oj.uz

Submission #380490

# Submission time Handle Problem Language Result Execution time Memory
380490 2021-03-22T04:04:39 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<vector<array<int, 2>>> bridge_tree;

vector<int> tin, low, comp, st;
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]) 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;

	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 = 'L';
		if(ans[i] > 0) c = 'R';
		cout << c;
	}

	return 0; 
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -