This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//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){
visited[u] = true;
for(auto x : G2[u]){
int v = x.first;
if (visited[v]) continue;
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));
}
cin >> q;
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);
while (q--){
int u, v;
cin >> u >> v;
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |