#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<char, int> ci;
typedef pair<string, int> si;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define inf INT_MAX/2
#define fro front
vector<vector<ii>> x(100005);
int vis[100005];
int hi[100005];
int bridges[100005];
vector<ii> rpath;
vector<ii> paths;
void recans(int node){
if(paths[node].first == -1){
return;
}else{
rpath.pb(ii(paths[node].second, paths[node].first));
recans(paths[node].first);
}
return;
}
int dfs(int n, int h, int pastn){
if(vis[n] == 2){
return 0;
}
if(vis[n] == 1){
return hi[n];
}
vis[n] = 1;
hi[n] = h;
int mi = inf;
int a = 1;
for(auto e:x[n]){
if(e.fi == pastn && a == 1){
a--;
continue;
}
int k = dfs(e.fi, h+1, n);
mi = min(k, mi);
if(k > h){
bridges[e.se] = 1;
}
}
vis[n] = 2;
return mi;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, p; cin >> n >> m;
vector<ii> d(m);
for(int i = 0; i < m; ++i){
int y, z; cin >> y >> z;
x[y].pb(ii(z, i));
x[z].pb(ii(y, i));
d[i] = ii(y, z);
}
for(int i = 1; i <= n; ++i){
hi[i] = inf;
}
for(int i = 1; i <= n; ++i){
if(vis[i] == 0){
dfs(i, 0, -1);
hi[i] = 0;
}
}
char dir[m];
for(int i = 0; i < m+1; ++i){
dir[i] = 'B';
}
cin >> p;
while(p--){
int u, v; cin >> u >> v;
int dist[n+1];
for(int i = 1; i <= n; ++i){
dist[i] = inf;
}
queue<int> q;
q.push(u);
dist[u] = 0;
vector<ii> path(m+1, ii(-1, -1));
while(!q.empty()){
int no = q.fro();
q.pop();
for(auto e:x[no]){
if(dist[e.fi] == inf){
path[e.fi] = ii(no, e.se);
q.push(e.fi);
dist[e.fi] = dist[no]+1;
}else{
continue;
}
}
}
paths = path;
recans(v);
reverse(whole(rpath));
for(int i = 0; i < rpath.size(); ++i){
if(bridges[rpath[i].first]){
if(rpath[i].se == d[rpath[i].fi].fi){
dir[rpath[i].first] = 'R';
}else{
dir[rpath[i].first] = 'L';
}
}
}
//cout << endl << endl;
rpath.clear();
paths.clear();
}
for(auto e:dir){
cout << e;
}
cout << endl;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i = 0; i < rpath.size(); ++i){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
