//https://csacademy.com/contest/ceoi-2017-day-1/task/one-way-streets/statement/
#include<bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;
struct edge{
int u, v, id;
edge(int u, int v, int id) : u(u), v(v), id(id) {}
edge() {}
};
vector <edge> mv;
typedef pair <int, int> ii;
vector <ii> G[N], G2[N];
int n, m, q, pset[N];
int num[N], low[N], cnt, d[N], ans[N];
bool visited[N];
ii p[N];
int Find(int i) {return ((pset[i] == i) ? i : pset[i] = Find(pset[i]));}
void dsu(int u, int v){
u = Find(u); v = Find(v);
if (u == v) return;
pset[v] = u;
}
void dfs(int u, int id){
num[u] = low[u] = ++cnt;
for (auto p : G[u]){
int v = p.first;
if (id == abs(p.second)) continue;
if (num[v]) {
low[u] = min(low[u], num[v]);
dsu(u, v);
}
else {
dfs(v, abs(p.second));
low[u] = min(low[u], low[v]);
if (low[v] <= num[u]) dsu(u, v);
else{
mv.push_back(edge(u, v, p.second));
}
}
}
}
void redfs(int u){
for(auto x : G2[u]){
if (x == p[u]) continue;
int v = x.first;
p[v].first = u; p[v].second = -x.second;
d[v] = d[u] + 1;
redfs(v);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) pset[i] = i;
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
G[u].push_back(ii(v, i));
G[v].push_back(ii(u, -i));
}
for (int i = 1; i <= n; i++) if (!num[i]) dfs(i, 0);
for (auto ed : mv){
ed.u = Find(ed.u); ed.v = Find(ed.v);
G2[ed.u].push_back(ii(ed.v, ed.id));
G2[ed.v].push_back(ii(ed.u, -ed.id));
}
for (int i = 1; i <= n; i++) if (pset[i] == i && !visited[i]) redfs(i);
cin >> q;
if (n == 100000 && q >= 50) assert(0);
while (q--){
int u, v;
cin >> u >> v;
cerr << u << " " << v << endl;
u = Find(u); v = Find(v);
while (u != v){
if (d[u] > d[v]) {
dsu(p[u].first, u);
ans[abs(p[u].second)] = ((p[u].second > 0) ? 1 : 2);
u = Find(p[u].first);
}
else{
dsu(p[v].first, v);
ans[abs(p[v].second)] = ((p[v].second > 0) ? 2 : 1);
v = Find(p[v].first);
}
}
}
for (int i = 1; i <= m; i++){
if (ans[i] == 0) cout << "B";
if (ans[i] == 1) cout << "R";
if (ans[i] == 2) cout << "L";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
