#include <bits/stdc++.h>
using namespace std;
int n, m, p;
int a[100005], b[100005], poc[100005], kraj[100005];
vector <pair <int, int> > v[100005];
vector <pair <int, int> > e[100005], be[100005];
int dt[100005], ft[100005], lw[100005];
int most[100005], blok[100005];
int brojac = 1;
int br1 = 1, br2 = 1;
int parent[100005];
int rez[100005];
map <int, int> mp[100005];
int find (int x){
if (parent[x] == x){
return x;
}
return parent[x] = find(parent[x]);
}
void unite (int x, int y){
int px = find(x);
int py = find(y);
if (px == py){
return;
}
if (mp[x].size() > mp[y].size()){
swap(px, py);
}
for (auto i : mp[px]){
mp[py][i.first]++;
if (mp[py][i.first] == 2){
mp[py].erase(i.first);
}
}
parent[px] = py;
return;
}
void dfs (int x, int p, int cesta){
lw[x] = dt[x];
for (int i = 0; i < v[x].size(); i++){
int x_novi = v[x][i].first;
int in = v[x][i].second;
if (dt[x_novi] == 0 and cesta != in){
e[x].push_back(make_pair(x_novi, in));
dt[x_novi] = br1;
parent[x_novi] = x_novi;
br1++;
dfs(x_novi, x, in);
lw[x] = min(lw[x], lw[x_novi]);
}
else
if (cesta != in){
be[x].push_back(make_pair(x_novi, in));
lw[x] = min(lw[x], dt[x_novi]);
}
}
if (cesta != -1 and lw[x] == dt[x]){
most[cesta] = 1;
}
ft[x] = br2;
br2++;
return;
}
void dfs2 (int x, int cesta){
for (int i = 0; i < e[x].size(); i++){
int x_novi = e[x][i].first;
int in = e[x][i].second;
dfs2(x_novi, in);
unite(x, x_novi);
}
int px = find(x);
if (cesta != -1 and mp[px].size() > 0){
for (auto i : mp[px]){
rez[cesta] = i.first;
break;
}
}
return;
}
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> a[i] >> b[i];
v[a[i]].push_back(make_pair(b[i], i));
v[b[i]].push_back(make_pair(a[i], i));
}
for (int i = 1; i <= n; i++){
if (blok[i] == 0){
blok[i] = brojac;
br1 = 1, br2 = 1;
dt[1] = br1;
br1++;
parent[i] = i;
dfs(i, 0, -1);
brojac++;
}
}
cin >> p;
for (int i = 1; i <= p; i++){
cin >> poc[i] >> kraj[i];
mp[poc[i]][i] = 1;
mp[kraj[i]][i] = 1;
}
dfs2(1, -1);
for (int i = 1; i <= m; i++){
if (rez[i] == 0 or most[i] == 0){
cout << "B";
}
else{
int k = kraj[rez[i]];
int p = poc[rez[i]];
//cout << a[i] << " " << b[i] << " " << p << " " << k << endl;
if ((dt[a[i]] < dt[b[i]] and dt[b[i]] <= dt[k] and ft[b[i]] >= ft[k]) or (dt[a[i]] > dt[b[i]] and dt[a[i]] <= dt[p] and ft[a[i]] >= ft[p])){
cout << "R";
}
else{
cout << "L";
}
}
}
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int, int)':
oneway.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < e[x].size(); i++){
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
14936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
