#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
vector<vector<int>> g(n);
vector<array<int,2>> edg;
for (int i=0;i<m;i++) {
int a,b;cin>>a>>b;a--;b--;
edg.push_back({a,b});
if (a==b) continue;
g[a].push_back(b);
g[b].push_back(a);
}
// calculate two-edge connected components
vector<int> low(n, 1e9), num(n, 0);
vector<vector<int>> cmp;
int timer=0;
stack<int> st;
function<void(int,int)> dfs=[&](int node, int parent) {
low[node]=num[node]=++timer;
st.push(node);
bool multiple = false;
for (int x:g[node]) {
if (x == parent && !multiple) {
multiple = true;
continue;
}
if (num[x] == 0) {
dfs(x,node);
low[node]=min(low[node],low[x]);
}
else {
low[node]=min(low[node],num[x]);
}
}
if (low[node] == num[node]) {
cmp.push_back({});
while (st.top() != node) {
cmp[cmp.size()-1].push_back(st.top());
st.pop();
}
cmp[cmp.size()-1].push_back(node);
st.pop();
}
};
for (int i=0;i<n;i++) {
if (num[i]==0) dfs(i,-1);
}
vector<int> idx(n, -1);
for (int i=0;i<cmp.size();i++) {
for (int x:cmp[i]) {
idx[x]=i;
}
}
vector<vector<int>> tree(cmp.size());
for (int i=0;i<n;i++) {
for (int x:g[i]) {
if (idx[x] != idx[i]) {
tree[idx[i]].push_back(idx[x]);
}
}
}
n=cmp.size();
vector<int> p(n,-1), d(n,0);
function<void(int,int)> dfs2=[&](int node, int parent) {
for (int x:tree[node]) {
if (x==parent)continue;
else if (p[x] != -1) continue;
p[x]=node;
d[x]=d[node]+1;
dfs2(x,node);
}
};
for (int i=0;i<n;i++) {
if (p[i]==-1)dfs2(i,-1);
}
vector<vector<int>> lft(n, vector<int>(20));
for (int i=0;i<n;i++) {
lft[i][0]=p[i];
}
for (int j=1;j<20;j++) {
for (int i=0;i<n;i++) {
lft[i][j]=lft[i][j-1];
if (lft[i][j] != -1) {
lft[i][j]=lft[lft[i][j]][j-1];
}
}
}
function<int(int,int)> jmp=[&](int a, int steps)->int{
int cnt=0;
while (steps) {
if ((steps&1)==1) {
a=lft[a][cnt];
if (a==-1)return -1;
}
steps>>=1;
cnt++;
}
return a;
};
function<int(int,int)> lca=[&](int a, int b) -> int {
if (d[a]<d[b])swap(a,b);
a=jmp(a,d[a]-d[b]);
if (a==b)return a;
for (int i=19;i>=0;i--) {
if (lft[a][i] != lft[b][i]) {
a=lft[a][i];
b=lft[b][i];
}
}
return lft[a][0];
};
int t;cin>>t;
vector<int> up(n, 0), down(n, 0);
for (int i=0;i<t;i++) {
int a,b;cin>>a>>b;a--;b--;
a=idx[a];b=idx[b];
if (a==b)continue;
int l=lca(a,b);
if (l == a) {
down[b]++;
down[a]--;
}
else if (l == b) {
up[b]--;
up[a]++;
}
else {
up[a]++;
down[b]++;
up[l]--;
down[l]--;
}
}
function<void(int,int)> dfs3=[&](int node, int pv) {
for (int x:tree[node]) {
if (x==pv)continue;
dfs3(x,node);
}
for (int x:tree[node]) {
if (x==pv)continue;
up[node]+=up[x];
down[node]+=down[x];
}
};
dfs3(0, -1);
for (auto x:edg) {
x[0]=idx[x[0]];
x[1]=idx[x[1]];
if (x[0]==x[1]) {
cout<<"B";
continue;
}
else if (d[x[0]] < d[x[1]]) {
if (up[x[1]] == 0 && down[x[1]] == 0) {
cout<<"B";
}
else if (up[x[1]] > down[x[1]]) {
cout<<"L";
}
else {
cout<<"R";
}
}
else {
if (up[x[0]] == 0 && down[x[0]] == 0) {
cout<<"B";
}
else if (up[x[0]] > down[x[0]]) {
cout<<"R";
}
else {
cout<<"L";
}
}
}
cout<<"\n";
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i=0;i<cmp.size();i++) {
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
856 KB |
Output is correct |
| 9 |
Correct |
1 ms |
600 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
856 KB |
Output is correct |
| 9 |
Correct |
1 ms |
600 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
33 ms |
5644 KB |
Output is correct |
| 12 |
Correct |
31 ms |
7148 KB |
Output is correct |
| 13 |
Correct |
36 ms |
9932 KB |
Output is correct |
| 14 |
Correct |
49 ms |
17092 KB |
Output is correct |
| 15 |
Incorrect |
52 ms |
20164 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
856 KB |
Output is correct |
| 9 |
Correct |
1 ms |
600 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
33 ms |
5644 KB |
Output is correct |
| 12 |
Correct |
31 ms |
7148 KB |
Output is correct |
| 13 |
Correct |
36 ms |
9932 KB |
Output is correct |
| 14 |
Correct |
49 ms |
17092 KB |
Output is correct |
| 15 |
Incorrect |
52 ms |
20164 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
