# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2e5+5;
long long u,vv,n,m,t,lc,a[N],out[N],lv[N],b[N],fix[N],in[N],tin,p[N][20],low[N],brd[N];
vector < pair <long long, long long > > v[N];
map < pair < int, int >, int > ind;
long long pa[N];
map < pair <long long, long long > , long long> ans,brdg;
char ch[N];
int get_col(int a)
{
if (a==pa[a]) return a;
return pa[a]=get_col(pa[a]);
}
void dfs(int a, int b)
{
fix[a]=1;
tin++;
in[a]=low[a]=tin;
lv[a]=lv[b]+1;
p[a][0]=b;
for (int i=1; i<=18; i++)
{
p[a][i]=p[p[a][i-1]][i-1];
}
for (int i=0; i<v[a].size(); i++)
{
if (v[a][i].f==b) continue;
if (fix[v[a][i].f])
{
low[a]=min(low[a],in[v[a][i].f]);
}
else
{
dfs(v[a][i].f,a);
low[a]=min(low[a],low[v[a][i].f]);
if (low[v[a][i].f]>in[a])
{
brdg[{v[a][i].f,a}]=1;
brdg[{a,v[a][i].f}]=1;
brd[v[a][i].s]=1;
}
}
}
out[a]=tin;
}
bool upper (int a, int b)
{
if (in[a]<=in[b] && out[a]>=out[b]) return true;
else return false;
}
int lca(int a, int b)
{
if (upper(b,a)) return b;
for (int i=18; i>=0; i--)
{
if (p[b][i] && !upper(p[b][i],a))
b=p[b][i];
}
return p[b][0];
}
int main()
{
cin>>n>>m;
for (int i=1; i<=m; i++)
{
cin>>a[i]>>b[i];
//if (a[i]==123 && b[i]==195) cout<<123<<" "<<195<<endl;
//if (a[i]==195 && b[i]==123) cout<<123<<" "<<195<<endl;
v[a[i]].pb({b[i],i});
v[b[i]].pb({a[i],i});
}
// cout<<a[987-21]<<" "<<b[987-21]<<endl;
for (int i=1; i<=n; i++)
{
if (!fix[i])
{
dfs(i,0);
}
}
for (int i=1; i<=m; i++)
{
//if (a[i]==123 && b[i]==195) cout<<ind[{a[i],b[i]}]<<endl;
// if (a[i]==195 && b[i]==123) cout<<ind[{a[i],b[i]}]<<endl;
if (ind[{a[i],b[i]}]!=0)
{
brdg[{a[i], b[i]}]=brdg[{b[i],a[i]}]=0;
brd[i]=0;
brd[ind[{a[i],b[i]}]]=0;
}
ind[{a[i],b[i]}]=i;
ind[{b[i],a[i]}]=i;
}
//cout<<brdg[{123,195}]<<endl;
for (int i=1; i<=n; i++)
{
pa[i]=i;
}
cin>>t;
while (t--)
{
cin>>u>>vv;
lc=lca(u,vv);
u=get_col(u);
while (lv[u]>lv[lc])
{
if (brdg[{u,p[u][0]}] || brdg[{p[u][0],u}])
{
ans[{u,p[u][0]}]=1;
}
pa[u]=p[u][0];
u=get_col(u);
}
vv=get_col(vv);
while (lv[vv]>lv[lc])
{
if (brdg[{vv,p[vv][0]}] || brdg[{p[vv][0],vv}]) ans[{p[vv][0],vv}]=1;
pa[vv]=p[vv][0];
vv=get_col(vv);
}
}
for (int i=1; i<=m; i++)
{
if (!brd[i])
{
cout<<"B";
continue;
}
if (ans[{a[i],b[i]}]==1) cout<<"R";
else if (ans[{b[i],a[i]}]==1) cout<<"L";
else cout<<"B";
}
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i=0; i<v[a].size(); i++)
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5484 KB |
Output is correct |
4 |
Correct |
6 ms |
5740 KB |
Output is correct |
5 |
Correct |
6 ms |
5740 KB |
Output is correct |
6 |
Correct |
5 ms |
5484 KB |
Output is correct |
7 |
Correct |
6 ms |
5740 KB |
Output is correct |
8 |
Correct |
6 ms |
5740 KB |
Output is correct |
9 |
Correct |
5 ms |
5484 KB |
Output is correct |
10 |
Correct |
5 ms |
5484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5484 KB |
Output is correct |
4 |
Correct |
6 ms |
5740 KB |
Output is correct |
5 |
Correct |
6 ms |
5740 KB |
Output is correct |
6 |
Correct |
5 ms |
5484 KB |
Output is correct |
7 |
Correct |
6 ms |
5740 KB |
Output is correct |
8 |
Correct |
6 ms |
5740 KB |
Output is correct |
9 |
Correct |
5 ms |
5484 KB |
Output is correct |
10 |
Correct |
5 ms |
5484 KB |
Output is correct |
11 |
Correct |
294 ms |
32876 KB |
Output is correct |
12 |
Correct |
335 ms |
38124 KB |
Output is correct |
13 |
Correct |
358 ms |
45364 KB |
Output is correct |
14 |
Correct |
399 ms |
55916 KB |
Output is correct |
15 |
Correct |
412 ms |
59244 KB |
Output is correct |
16 |
Correct |
581 ms |
71788 KB |
Output is correct |
17 |
Correct |
554 ms |
73452 KB |
Output is correct |
18 |
Correct |
593 ms |
71916 KB |
Output is correct |
19 |
Correct |
539 ms |
75500 KB |
Output is correct |
20 |
Correct |
277 ms |
40684 KB |
Output is correct |
21 |
Correct |
251 ms |
39768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5484 KB |
Output is correct |
4 |
Correct |
6 ms |
5740 KB |
Output is correct |
5 |
Correct |
6 ms |
5740 KB |
Output is correct |
6 |
Correct |
5 ms |
5484 KB |
Output is correct |
7 |
Correct |
6 ms |
5740 KB |
Output is correct |
8 |
Correct |
6 ms |
5740 KB |
Output is correct |
9 |
Correct |
5 ms |
5484 KB |
Output is correct |
10 |
Correct |
5 ms |
5484 KB |
Output is correct |
11 |
Correct |
294 ms |
32876 KB |
Output is correct |
12 |
Correct |
335 ms |
38124 KB |
Output is correct |
13 |
Correct |
358 ms |
45364 KB |
Output is correct |
14 |
Correct |
399 ms |
55916 KB |
Output is correct |
15 |
Correct |
412 ms |
59244 KB |
Output is correct |
16 |
Correct |
581 ms |
71788 KB |
Output is correct |
17 |
Correct |
554 ms |
73452 KB |
Output is correct |
18 |
Correct |
593 ms |
71916 KB |
Output is correct |
19 |
Correct |
539 ms |
75500 KB |
Output is correct |
20 |
Correct |
277 ms |
40684 KB |
Output is correct |
21 |
Correct |
251 ms |
39768 KB |
Output is correct |
22 |
Correct |
775 ms |
72940 KB |
Output is correct |
23 |
Correct |
758 ms |
69996 KB |
Output is correct |
24 |
Correct |
809 ms |
70052 KB |
Output is correct |
25 |
Correct |
836 ms |
78384 KB |
Output is correct |
26 |
Correct |
793 ms |
72248 KB |
Output is correct |
27 |
Correct |
772 ms |
70252 KB |
Output is correct |
28 |
Correct |
192 ms |
13548 KB |
Output is correct |
29 |
Correct |
430 ms |
44396 KB |
Output is correct |
30 |
Correct |
437 ms |
45036 KB |
Output is correct |
31 |
Correct |
452 ms |
45180 KB |
Output is correct |
32 |
Correct |
571 ms |
53228 KB |
Output is correct |