#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,m;
pair<int,int> edge[MAXN];
vector<pair<int,int> > adj[MAXN];
int par[MAXN];
int dep[MAXN];
int low[MAXN];
bool vis[MAXN];
bool bri[MAXN];
int ctr=0;
void dfs(int x){
vis[x]=1;
dep[x]=low[x]=ctr++;
for(int i=0;i<(int)adj[x].size();i++){
int y=adj[x][i].first;
if(!vis[y]){ //not yet visited
par[y]=x;
dfs(y);
if(low[y]>dep[x])bri[adj[x][i].second]=1;
low[x]=min(low[x],low[y]);
}else if(y!=par[x])low[x]=min(low[x],dep[y]); //visited and is not parent
}
}
int scc[MAXN];
int c=0;
void comp(int x){
scc[x]=c;
for(int i=0;i<(int)adj[x].size();i++){
if(!bri[adj[x][i].second]&&scc[adj[x][i].first]==-1)comp(adj[x][i].first);
}
}
vector<pair<int,int> > adj2[MAXN];
pair<int,int> q[MAXN];
vector<pair<int,int> > r;
int pa[MAXN][19],idx[MAXN];
int ldep[MAXN];
void dfs2(int x){
vis[x]=1;
for(int i=0;i<(int)(adj2[x].size());i++){
int y=adj2[x][i].first;
if(!vis[y]){
pa[y][0]=x;idx[y]=adj2[x][i].second;
ldep[y]=ldep[x]+1;
dfs2(y);
}
}
}
int lca(int x,int y){
if(x==y)return x;
if(ldep[x]<ldep[y])swap(x,y);
for(int i=18;i>=0;i--){
if(pa[x][i]!=-1&&ldep[pa[x][i]]>=ldep[y])x=pa[x][i];
}
if(x==y)return x;
for(int i=18;i>=0;i--){
if(pa[x][i]!=pa[y][i]){x=pa[x][i];y=pa[y][i];}
}
return pa[x][0];
}
int ans[MAXN]; //0 B, 1 R, -1 L
void dir(int x,int y,int d){
if(x==y)return;
if(ans[idx[x]]!=0)return;
int a=edge[idx[x]].first,b=edge[idx[x]].second;
if(x==scc[a]){
ans[idx[x]]=d;dir(scc[b],y,d);
}else{
ans[idx[x]]=-d;dir(scc[a],y,d);
}
}
int main(){
scanf("%d%d",&n,&m);
memset(par,-1,sizeof(par));memset(dep,-1,sizeof(dep));memset(low,-1,sizeof(low));
memset(scc,-1,sizeof(scc));
memset(pa,-1,sizeof(pa));memset(idx,-1,sizeof(idx));memset(ldep,-1,sizeof(ldep));
int a,b;
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);a--;b--;edge[i]=make_pair(a,b);
adj[a].push_back(make_pair(b,i));adj[b].push_back(make_pair(a,i));
}
for(int i=0;i<n;i++)if(!vis[i])dfs(i);
//for(int i=0;i<m;i++)if(bri[i])printf("1 ");else printf("0 ");printf("\n");
for(int i=0;i<n;i++)if(scc[i]==-1){comp(i);c++;}
for(int i=0;i<m;i++){
if(bri[i]){
a=edge[i].first,b=edge[i].second;
adj2[scc[a]].push_back(make_pair(scc[b],i));adj2[scc[b]].push_back(make_pair(scc[a],i));
}
}
//for(int i=0;i<n;i++)printf("%d ",scc[i]);printf("\n");
for(int i=0;i<c;i++)vis[i]=0; for(int i=0;i<c;i++)if(!vis[i]){ldep[i]=0;dfs2(i);}
for(int i=1;i<18;i++)for(int j=0;j<c;j++)if(pa[j][i-1]!=-1)pa[j][i]=pa[pa[j][i-1]][i-1];
int p;scanf("%d",&p);
for(int i=0;i<p;i++){
scanf("%d%d",&q[i].first,&q[i].second);q[i].first--;q[i].second--;
if(scc[q[i].first]==scc[q[i].second])continue;
r.push_back(make_pair(lca(scc[q[i].first],scc[q[i].second]),i));
}
sort(r.begin(),r.end());
for(int i=0;i<(int)r.size();i++){
a=q[r[i].second].first,b=q[r[i].second].second;
//printf("%d->%d->%d\n",a,r[i].first,b);
dir(scc[a],r[i].first,1);
dir(scc[b],r[i].first,-1);
}
for(int i=0;i<m;i++){
if(ans[i]==0)printf("B");
else if(ans[i]==1)printf("R");
else printf("L");
}
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:100:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=0;i<c;i++)vis[i]=0; for(int i=0;i<c;i++)if(!vis[i]){ldep[i]=0;dfs2(i);}
^~~
oneway.cpp:100:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=0;i<c;i++)vis[i]=0; for(int i=0;i<c;i++)if(!vis[i]){ldep[i]=0;dfs2(i);}
^~~
oneway.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
oneway.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);a--;b--;edge[i]=make_pair(a,b);
~~~~~^~~~~~~~~~~~~~
oneway.cpp:102:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int p;scanf("%d",&p);
~~~~~^~~~~~~~~
oneway.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&q[i].first,&q[i].second);q[i].first--;q[i].second--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
12 ms |
14848 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14848 KB |
Output is correct |
| 4 |
Correct |
13 ms |
14976 KB |
Output is correct |
| 5 |
Incorrect |
14 ms |
14976 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
12 ms |
14848 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14848 KB |
Output is correct |
| 4 |
Correct |
13 ms |
14976 KB |
Output is correct |
| 5 |
Incorrect |
14 ms |
14976 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
14848 KB |
Output is correct |
| 2 |
Correct |
12 ms |
14848 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14848 KB |
Output is correct |
| 4 |
Correct |
13 ms |
14976 KB |
Output is correct |
| 5 |
Incorrect |
14 ms |
14976 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
