#include <bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int>::max() / 2;
vector<int> num, low, comp;
stack<int> s;
int dfs_count = 0;
int comp_count = 0;
vector<vector<int>> dir;
vector<int> in;
vector<int> out;
void tarjan_dfs(int current, int parent, vector<vector<int>>& adj) {
num[current] = low[current] = dfs_count;
dfs_count++;
s.push(current);
for (int neigh : adj[current]) {
if (num[neigh] == INF) {
tarjan_dfs(neigh, current, adj);
low[current] = min(low[current], low[neigh]);
if (num[neigh] == low[neigh]) {
while (s.top() != neigh) {
int top = s.top();
s.pop();
comp[top] = comp_count;
}
s.pop();
comp[neigh] = comp_count;
comp_count++;
}
} else if (neigh != parent) {
low[current] = min(low[current], num[neigh]);
}
}
}
int dir_dfs(int current, vector<int>& visited, vector<vector<int>>& adj) {
visited[current] = 1;
int incoming = in[current] - out[current];
for (int neigh : adj[current]) {
if (visited[neigh] == 0) {
int d = dir_dfs(neigh, visited, adj);
if (d < 0) {
dir[current][neigh] = -1;
dir[neigh][current] = 1;
} else {
dir[current][neigh] = 1;
dir[neigh][current] = -1;
}
incoming += d;
}
}
return incoming;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
vector<pair<int, int>> streets;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
streets.push_back(make_pair(a, b));
}
int p;
cin >> p;
vector<pair<int, int>> pairs;
for (int i = 0; i < p; i++) {
int a, b;
cin >> a >> b;
a--; b--;
pairs.push_back(make_pair(a, b));
}
num = vector<int>(n, INF);
low = vector<int>(n);
comp = vector<int>(n);
for (int i = 0; i < n; i++) {
if (num[i] == INF) {
tarjan_dfs(i, i, adj);
while (!s.empty()) {
int top = s.top();
s.pop();
comp[top] = comp_count;
}
comp_count++;
}
}
adj = vector<vector<int>>(comp_count);
for (pair<int, int> s : streets) {
if (comp[s.first] != comp[s.second]) {
adj[comp[s.first]].push_back(comp[s.second]);
adj[comp[s.second]].push_back(comp[s.first]);
}
}
in = vector<int>(comp_count, 0);
out = vector<int>(comp_count, 0);
for (pair<int, int> p : pairs) {
if (comp[p.first] != comp[p.second]) {
out[comp[p.first]]++;
in[comp[p.second]]++;
}
}
vector<int> visited(comp_count, 0);
dir = vector<vector<int>>(comp_count, vector<int>(comp_count, 0));
for (int i = 0; i < comp_count; i++) {
if (visited[i] == 0) dir_dfs(i, visited, adj);
}
for (pair<int, int> s : streets) {
if (comp[s.first] == comp[s.second] || dir[comp[s.first]][comp[s.second]] == 0) cout << "B";
else if (dir[comp[s.first]][comp[s.second]] == 1) cout << "R";
else cout << "L";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
