/*input
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int N2=20;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl
//Trace prints the name of the variable and the value.
int n, m, P;vector< pii > adj[N], adjlist[N];
pii arr[N];int disc[N], low[N], cur, cno[N], p[N][N2], addu[N], addv[N], sub[N],ent[N], ex[N], depth[N];
bool art[N];bool dup[N];string ans;
vector< pii > edges;
void dfs(int i, int p)
{
// cout<<i<<" ";
disc[i]=cur++;low[i]=disc[i];
int ct=0;
for(auto &j:adj[i])
{
if(j.f==p) ct++;
if(j.f==p) continue;
if(disc[j.f]==inf)
{
dfs(j.f, i);
if(low[j.f]>disc[i]) art[j.s]=1;
low[i]=min(low[i], low[j.f]);
}
else
{
low[i]=disc[j.f];
}
}
if(ct>1)
for(auto j:adj[i])
if(j.f==p) dup[j.s]=1;
}
void dfs2(int i)
{
cno[i]=cur;
for(auto j:adj[i])
{
if(art[j.s]) adjlist[cur].push_back(j);
if(cno[j.f]!=-1||art[j.s]) continue;
dfs2(j.f);
}
}
void dfs3(int i)
{
for(auto j:adjlist[i])
{
if(j.f==p[i][0]) continue;
depth[j.f]=depth[i]+1;
p[j.f][0]=i;dfs3(j.f);
}
}
int LCA(int u, int v)
{
if(depth[u]>depth[v]) swap(u, v);
int diff=depth[v]-depth[u];
for(int i=N2-1;i>=0;i--)
{
if((1<<i)<=diff)
{
diff-=(1<<i);v=p[v][i];
}
}
if(u==v) return u;
for(int i=N2-1;i>=0;i--)
{
if(p[u][i]!=p[v][i]) {u=p[u][i];v=p[v][i];}
}
return p[u][0];
}
void dfsf(int i)
{
int pind;
for(auto j:adjlist[i])
{
if(j.f==p[i][0]) {
pind=j.s;
continue;}
dfsf(j.f);ex[i]+=ex[j.f];ent[i]+=ent[j.f];
}
ent[i]-=sub[i];ex[i]-=sub[i];ent[i]+=addv[i];ex[i]+=addu[i];
if(ent[i]>0)
{
int u=edges[pind].f, v=edges[pind].s;
u=cno[u];v=cno[v];
if(v==i) ans[pind]='R';
else ans[pind]='L';
}
else if(ex[i]>0)
{
int u=edges[pind].f, v=edges[pind].s;
u=cno[u];v=cno[v];
if(v==i) ans[pind]='L';
else ans[pind]='R';
}
// cout<<i<<": "<<ent[i]<<" "<<ex[i]<<endl;
}
void solve()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
art[i]=0;dup[i]=0;
int u, v;cin>>u>>v;adj[u].push_back(mp(v, i));adj[v].push_back(mp(u, i));edges.push_back(mp(u, v));
}
cin>>P;
for(int i=0;i<m;i++) ans.push_back('B');
for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
for(int i=1;i<=n;i++) {disc[i]=inf;cno[i]=-1;addu[i]=addv[i]=ent[i]=ex[i]=0;}
cur=1;
dfs(1, 1);
for(int i=0;i<m;i++)
if(dup[i]) art[i]=0;cur=1;
for(int i=1;i<=n;i++)
{
if(cno[i]==-1) {dfs2(i);cur++;}
}
for(int i=1;i<cur;i++)
for(auto &j:adjlist[i]) j.f=cno[j.f];
cur--;p[1][0]=1;depth[1]=0;
/* for(int i=1;i<=cur;i++)
{
cout<<i<<": ";
for(auto j:adjlist[i]) cout<<j.f<<" "<<j.s<<endl;
}*/
dfs3(1);
for(int j=1;j<N2;j++)
for(int i=1;i<=n;i++) p[i][j]=p[p[i][j-1]][j-1];
for(auto i:arr)
{
i.f=cno[i.f], i.s=cno[i.s];
addu[i.f]++;addv[i.s]++;
int u=LCA(i.f, i.s);
sub[u]++;
}
dfsf(1);
cout<<ans;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
while(t--)
{
solve();
}
}
Compilation message
oneway.cpp: In function 'void solve()':
oneway.cpp:129:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
^~~
oneway.cpp:129:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=1;i<=P;i++) cin>>arr[i].f>>arr[i].s;cur=1;
^~~
oneway.cpp:134:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(dup[i]) art[i]=0;cur=1;
^~
oneway.cpp:134:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(dup[i]) art[i]=0;cur=1;
^~~
oneway.cpp:133:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=0;i<m;i++)
^~~
oneway.cpp:134:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
if(dup[i]) art[i]=0;cur=1;
^~~
oneway.cpp: In function 'void dfsf(long long int)':
oneway.cpp:105:19: warning: 'pind' may be used uninitialized in this function [-Wmaybe-uninitialized]
int u=edges[pind].f, v=edges[pind].s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
