#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
vi stck;
vector<vii> g;
vii ed;
string a = "";
vi v;
vi UFDS;
vi usd;
int pt(int n){
if(UFDS[n]==n)
return n;
else
return UFDS[n] = pt(UFDS[n]);
}
int mrg(int l, int r){
return UFDS[pt(l)] = pt(r);
}
bool dfs_cycle(int n, int p){
if(v[n]){
/* for(int x=0; x<stck.size(); x++){
if(ed[stck[x]].first==n||ed[stck[x]].second==n){
if(x!=0)
x++;
while(x<stck.size()){
cout << n << " " << stck[x] << endl;
a[stck[x]] = 'B';
x++;
}
}
*/ //}
a[p] = 'B';
return 1;
}
v[n] = 1;
bool c = 0;
for(int x=0; x<g[n].size(); x++){
if(g[n][x].second!=p&&!usd[g[n][x].second]){
stck.push_back(g[n][x].second);
usd[g[n][x].second] = 1;
if(dfs_cycle(g[n][x].first, g[n][x].second)){
mrg(g[n][x].first, n);
c = 1;
}
usd[g[n][x].second] = 0;
}
}
v[n] = 0;
return c;
}
bool dfs_path(int n, int d){
if(v[n])
return 0;
if(n==d){
return 1;
}
v[n] = 1;
bool r = 0;
for(int x=0; x<g[n].size(); x++){
if(!v[g[n][x].first]){
//not visited yet
if(dfs_path(g[n][x].first, d)){
//reachable
if(a[g[n][x].second]=='0'){
if(ed[g[n][x].second].first==n){
//from first to second
a[g[n][x].second] = 'R';
} else {
a[g[n][x].second] = 'L';
}
}
r=1;
}
}
}
//v[n] = 0;
return r;
}
int main(){
int N, M, P; cin>>N>>M;
a = string(M, '0');
int A, B;
g.assign(N+1, vii());
for(int m=0; m<M; m++){
cin>>A>>B;
g[A].push_back({B, m});
g[B].push_back({A, m});
ed.push_back({A, B});
}
UFDS.assign(N+1, 0);
usd.assign(M+1, 0);
for(int n=0; n<=N; n++)
UFDS[n] = n;
v.assign(N+1, 0);
for(int n=1; n<=N; n++){
// v.assign(N+1, 0);
if(!v[n]){
dfs_cycle(n, -1);
}
}
cin>>P;
//cout << a << endl;
for(int p=0; p<P; p++){
cin>>A>>B;
//find path from A to B, changing edges on the way
v.assign(N+1, 0);
dfs_path(A, B);
}
// cout << a << endl;
for(int x=0; x<M; x++){
if(a[x]=='0')
a[x] = 'B';
}
cout << a << endl;
return 0;
}
Compilation message
oneway.cpp: In function 'bool dfs_cycle(int, int)':
oneway.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0; x<g[n].size(); x++){
~^~~~~~~~~~~~
oneway.cpp: In function 'bool dfs_path(int, int)':
oneway.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int x=0; x<g[n].size(); x++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Runtime error |
1102 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Runtime error |
1102 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Runtime error |
1102 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
