#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int , int>>> adj;
vector<int> depth;
vector<int> dp;
vector<int> pref;
vector<char> ans;
vector<pair<int ,int>> edges;
void dfs(int x)
{
for(auto [u , i] : adj[x])
{
if(depth[u] == 0)
{
depth[u] = depth[x] + 1;
dfs(u);
dp[x]+=dp[u];
}
else if(depth[u] < depth[x])
{
dp[x]++;
}
else if(depth[u] > depth[x])
{
dp[x]--;
}
}
dp[x]--;
}
void dfs1(int x)
{
for(auto [u , i] : adj[x])
{
if(depth[u] == 0)
{
depth[u] = depth[x] + 1;
dfs1(u);
if(dp[u] == 0 && pref[u])
{
int m1 = (u == edges[i].first ? 1 : -1);
int m2 = (pref[u] > 0 ? 1 : -1);
if(m1 * m2 > 0)
{
ans[i] = 'R';
}
else
ans[i] = 'L';
}
pref[x]+=pref[u];
}
}
}
int main()
{
int n , m;
cin>>n>>m;
adj = vector<vector<pair<int, int>>> (n + 1);
depth = vector<int> (n + 1);
dp = depth;
pref = depth;
edges.assign(m , {});
ans.assign(m , 'B');
for(int i = 0 ; i < m; i++)
{
int x ,y;
cin>>x>>y;
edges[i] = {x , y};
adj[x].push_back({y , i});
adj[y].push_back({x , i});
}
depth[1] = 1;
dfs(1);
int p ;
cin>>p;
for(int i = 0 ; i < p ; i++)
{
int x , y;
cin>>x>>y;
pref[x]++;
pref[y]--;
}
depth.assign(n + 1 , 0);
depth[1] = 1;
dfs1(1);
for(int i = 0 ;i < m; i++)
cout<<ans[i];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
