#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,p,i,x[101010],y[101010],X[101010],Y[101010],j,te,JK;
vector<ll> v[101010],w[101010],V[101010],isi[101010],W[101010];
ll b[101010];
ll nm[101010];
ll Z[101010];
ll br[101010];
ll wk[101010];
ll mi[101010];
string s;
pair<ll,ll> P[101010];
void dfs(ll aa,ll bb)
{
te++;
wk[aa]=te;
mi[aa]=te;
b[aa]=1;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
{
if(abs(w[aa][ii])==bb)continue;
if(b[v[aa][ii]]==0)
{
dfs(v[aa][ii],abs(w[aa][ii]));
mi[aa]=min(mi[aa],mi[v[aa][ii]]);
if(wk[aa]<mi[v[aa][ii]])
{
br[abs(w[aa][ii])]=1;
//cout<<aa<<" "<<v[aa][ii]<<"\n";
}
}
else
{
mi[aa]=min(mi[aa],wk[v[aa][ii]]);
}
}
}
void dfs2(ll aa)
{
b[aa]=1;
nm[aa]=JK;
isi[JK].pb(aa);
ll ii;
for(ii=0;ii<v[aa].size();ii++)
{
if(br[abs(w[aa][ii])])continue;
if(b[v[aa][ii]])continue;
dfs2(v[aa][ii]);
}
}
void dfs3(ll aa,ll bb)
{
b[aa]=1;
ll ii;
for(ii=0;ii<V[aa].size();ii++)
{
if(b[V[aa][ii]])continue;
if(bb)
{
if((w[aa][ii]*bb)>0LL)
s[abs(w[aa][ii])]='R';
else
s[abs(w[aa][ii])]='L';
}
dfs3(V[aa][ii],bb+Z[V[aa][ii]]);
}
}
void dfs4(ll aa,ll bb)
{
ll ii;
for(ii=0;ii<V[aa].size();ii++)
if(V[aa][ii]!=bb)
{
P[V[aa][ii]]=mp(aa,W[aa][ii]);
dfs4(V[aa][ii],aa);
}
}
int main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>x[i]>>y[i];
v[x[i]].pb(y[i]);
w[x[i]].pb(i);
v[y[i]].pb(x[i]);
w[y[i]].pb(-i);
s+="B";
}
cin>>p;
for(i=1;i<=p;i++)cin>>X[i]>>Y[i];
for(i=1;i<=n;i++)
{
if(!b[i])
{
dfs(i,i);
break;
}
}
memset(b,0,sizeof(b));
for(i=1;i<=n;i++)
if(!b[i])
{
JK++;
dfs2(i);
}
//return 0;
for(i=1;i<=m;i++)
if(br[i])
{
// cout<<nm[x[i]]<<" "<<nm[y[i]]<<"_\n";
V[nm[x[i]]].pb(nm[y[i]]);
W[nm[x[i]]].pb(i);
V[nm[y[i]]].pb(nm[x[i]]);
W[nm[y[i]]].pb(-i);
}
for(i=1;i<=p;i++)
{
dfs4(nm[X[i]],nm[X[i]]);
P[nm[X[i]]]=mp(-1,-1);
ll tem=nm[Y[i]];
while(tem!=nm[X[i]])
{
//cout<<abs(P[tem].se)<<"_\n";
if(P[tem].se<0)
s[abs(P[tem].se)-1]='L';
else
s[abs(P[tem].se)-1]='R';
tem=P[tem].fi;
//cout<<tem<<"\n";
//break;
}
//cout<<nm[X[i]]<<" "<<nm[Y[i]]<<"\n";
//Z[nm[X[i]]]++;
//Z[nm[Y[i]]]--;
}
cout<<s<<"\n";
//return 0;
memset(b,0,sizeof(b));
for(i=1;i<=JK;i++)
{
if(!b[i])
{
dfs3(i,Z[i]);
}
}
}
Compilation message
oneway.cpp: In function 'void dfs(ll, ll)':
oneway.cpp:25:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(ll)':
oneway.cpp:50:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(ll, ll)':
oneway.cpp:61:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<V[aa].size();ii++)
~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs4(ll, ll)':
oneway.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<V[aa].size();ii++)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
13048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
13048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
13048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
