#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,k,disc[100001],low[100001],cnt,p[100001][18],val_up[100001],val_down[100001],level[100001];
pii edge[100001];
char ans[100001];
vector<pii> adj[100001];
bool bridge[100001],vis[100001];
void tarjan(int x, int line) {
disc[x]=low[x]=++cnt;
for (auto s : adj[x]) {
if (s.second==line) continue;
if (disc[s.first]) low[x]=min(low[x],disc[s.first]);
else {
tarjan(s.first,s.second);
if (s.second==1) cout<<"Yes";
low[x]=min(low[x],low[s.first]);
if (low[s.first]>disc[x]) bridge[s.second]=true;
}
}
}
/*
void dfs1(int x, int par) {
vis[x]=true;
level[x]=level[par]+1;
p[x][0]=par;
for (int i=1; i<=17; ++i) p[x][i]=p[p[x][i-1]][i-1];
for (auto s : adj[x]) {
if (vis[s.first]) continue;
dfs1(s.first,x);
}
}
int lca(int x, int y) {
if (level[y]>level[x]) swap(x,y);
int dif=level[x]-level[y];
for (int i=0; i<18; ++i) {
if (dif&(1<<i)) x=p[x][i];
}
if (x==y) return x;
for (int i=17; i>=0; --i) {
if (p[x][i]!=p[y][i]) {
x=p[x][i];
y=p[y][i];
}
}
return p[x][0];
} */
void dfs2(int x) {
vis[x]=true;
for (auto s : adj[x]) {
if (vis[s.first]) continue;
dfs2(s.first);
val_up[x]+=val_up[s.first];
val_down[x]+=val_down[s.first];
if (bridge[s.second]) {
if (val_up[s.first]>0) { //s.first to x
if (edge[s.second].first==x) ans[s.second]='L';
else ans[s.second]='R';
} else if (val_down[s.first]>0) { //x to s.first
if (edge[s.second].first==x) ans[s.second]='R';
else ans[s.second]='L';
} else {
ans[s.second]='B';
}
}
}
}
bool vis_noob[1001];
bool dfs_noob(int x, int ed) {
vis_noob[x]=true;
if (x==ed) return true;
for (auto s : adj[x]) {
if (vis_noob[s.first]) continue;
if (dfs_noob(s.first,ed)) { //x to s.first
if (bridge[s.second]) {
if (edge[s.second].first==x) ans[s.second]='R';
else ans[s.second]='L';
}
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for (int i=0; i<m; ++i) {
int a,b; cin>>a>>b;
adj[a].push_back(pii(b,i));
adj[b].push_back(pii(a,i));
edge[i]=pii(a,b);
}
tarjan(1,-1);
//dfs1(1,0);
int q; cin>>q;
while (q--) {
int a,b; cin>>a>>b;
memset(vis_noob,0,sizeof(vis_noob));
dfs_noob(a,b);
/*
int LCA=lca(a,b);
++val_up[a]; --val_up[LCA];
++val_down[b]; --val_down[LCA]; */
}
/*
memset(vis,0,sizeof(vis));
dfs2(1); */
for (int i=0; i<m; ++i) {
if (!ans[i]) cout<<'B';
else cout<<ans[i];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
