#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;
const int oo = INT_MAX;
int n,m,k;
pair<int,int> e[nmax + 5];
vector<pair<int,int>> G[nmax + 5];
bool sel[nmax + 5];
int lvl[nmax + 5], r[nmax + 5];
int p[nmax + 5], u[nmax + 5];
vector<pair<int,int>> rst;
vector<int> out[nmax + 5], in[nmax + 5];
int cnt = 0;
char rez[nmax + 5];
vector<int> l_sel;
int Min_px[nmax + 5], Max_px[nmax + 5], Min_py[nmax + 5], Max_py[nmax + 5];
void dfs(int nod, int nr = 0)
{
l_sel.push_back(nod);
p[nod] = (++cnt);
sel[nod] = true;
r[nod] = lvl[nod];
for(auto it : G[nod])
{
if(sel[it.first])
{
if(it.second!=nr)
{
r[nod] = min(r[nod], lvl[it.first]);
}
continue;
}
lvl[it.first] = 1 + lvl[nod];
dfs(it.first,it.second);
r[nod] = min(r[nod], r[it.first]);
}
u[nod] = cnt;
}
void solve(int nod, int nr = 0)
{
sel[nod] = true;
for(auto it : G[nod])
{
if(sel[it.first])
{
if(it.second!=nr)
{
rez[it.second] = 'B';
}
continue;
}
solve(it.first,it.second);
}
Min_px[nod] = oo, Max_px[nod] = 0, Min_py[nod] = oo, Min_px[nod] = 0;
for(auto x : in[nod])
{
Min_px[nod] = min(Min_px[nod], p[x]);
Max_px[nod] = max(Max_px[nod], p[x]);
}
for(auto y : out[nod])
{
Min_py[nod] = min(Min_py[nod], p[y]);
Max_py[nod] = max(Max_py[nod], p[y]);
}
for(auto it : G[nod])
{
if(sel[it.first])
{
continue;
}
Min_px[nod] = min(Min_px[nod], Min_px[it.first]);
Max_px[nod] = max(Max_px[nod], Max_px[it.first]);
Min_py[nod] = min(Min_py[nod], Min_py[it.first]);
Max_py[nod] = max(Max_py[nod], Max_py[it.first]);
}
if(!nr)
{
return;
}
if(r[nod] < lvl[nod])
{
rez[nr] = 'B';
return;
}
bool sus = false, jos = false;
if(Min_px[nod] < p[nod] || Max_px[nod] > u[nod])
{
jos = true;
}
if(Min_py[nod] < p[nod] || Max_py[nod] > u[nod])
{
sus = true;
}
if(jos)
{
if(e[nr].second == nod)
{
rez[nr] = 'R';
}
else
{
rez[nr] = 'L';
}
}
if(sus)
{
if(e[nr].second == nod)
{
rez[nr] = 'L';
}
else
{
rez[nr] = 'R';
}
}
if(!sus && !jos)
{
rez[nr] = 'B';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
e[i] = {x,y};
if(x==y)
{
rez[i] = 'B';
continue;
}
G[x].push_back({y,i});
G[y].push_back({x,i});
}
cin>>k;
for(int i=1; i<=k; i++)
{
int x,y;
cin>>x>>y;
out[x].push_back(y);
in[y].push_back(x);
rst.push_back({x,y});
}
for(int i=1; i<=n; i++)
{
if(!sel[i])
{
l_sel.clear();
dfs(i);
for(auto it : l_sel)
{
sel[it] = false;
}
solve(i);
}
}
cout<<rez+1<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
