#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];
int dt[100005], ft[100005], lw[100005];
int most[100005], blok[100005], d[100005];
int brojac = 1;
int br1 = 1, br2 = 1;
int parent[100005], par[100005];
int rez[100005], ans[100005], max_lca[100005];
int go[100005][17];
bool isbroj(char x) {
return x >= '0' && x <= '9';
}
long long unos() {
long long res = 0;
char ch;
while (!isbroj(ch = getchar()));
res = ch - '0';
while (isbroj(ch = getchar())) {
res = res * 10 + ch - '0';
}
return res;
}
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(parent[x]);
int py = find(parent[y]);
if (px == py){
return;
}
//cout << px << " " << py << endl;
if (ans[px] != 0 and ans[px] == ans[py]){
ans[px] = 0;
ans[py] = 0;
max_lca[px] = 0;
max_lca[py] = 0;
}
if (d[max_lca[px]] < d[max_lca[py]] or ans[py] == 0){
parent[py] = px;
}
else{
parent[px] = py;
}
/*
if (mp[x].size() > mp[y].size()){
swap(px, py);
}
*/
/*
for (auto i : mp[px]){
if (mp[py][i.first] == 1){
mp[py].erase(i.first);
}
else{
mp[py][i.first] = 1;
}
}
mp[px].clear();
/*
while (mp[px].size() > 0){
//mp[px].begin();
it = mp[px].begin();
mp[py][it -> first]++;
if (mp[py][it -> first] == 2){
mp[py].erase(it -> first);
}
mp[px].erase(mp[px].begin());
}
*/
//parent[px] = py;
return;
}
void dfs (int x, int p, int cesta){
//cout << " aaa " << x << " " << p << endl;
blok[x] = brojac;
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 and x != x_novi){
e[x].push_back(make_pair(x_novi, in));
dt[x_novi] = br1;
parent[x_novi] = x_novi;
par[x_novi] = x;
br1++;
d[x_novi] = d[x] + 1;
dfs(x_novi, x, in);
lw[x] = min(lw[x], lw[x_novi]);
}
else
if (cesta != in and x != x_novi){
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){
rez[cesta] = ans[px];
}
return;
}
int idi (int x, int i){
//cout << x << " " << i << endl;
if (go[x][i] != -1){
return go[x][i];
}
if (i == 0){
go[x][i] = par[x];
return go[x][i];
}
int pola = idi(x, i - 1);
go[x][i] = idi(pola, i - 1);
return go[x][i];
}
int lca (int x, int y){
if (blok[x] != blok[y]){
return 0;
}
if (d[x] < d[y]){
swap(x, y);
}
//cout << " aaa " << x << " " << y << endl;
for (int i = 16; i >= 0; i--){
int novi_x = idi(x, i);
if (d[novi_x] >= d[y]){
x = novi_x;
}
}
//cout << " bbb " << x << " " << y << endl;
if (x == y){
return x;
}
for (int i = 16; i >= 0; i--){
int novi_x = idi(x, i);
int novi_y = idi(y, i);
if (novi_x != novi_y){
x = novi_x;
y = novi_y;
}
}
return par[x];
}
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(go, -1, sizeof go);
n = unos();
m = unos();
for (int i = 1; i <= m; i++){
a[i] = unos();
b[i] = unos();
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){
d[i] = 1;
blok[i] = brojac;
br1 = 1, br2 = 1;
dt[i] = 1;
br1++;
parent[i] = i;
par[i] = i;
dfs(i, 0, -1);
brojac++;
}
}
/*
for (int i = 1; i <= n; i++){
cout << blok[i] << endl;
cout << i << " : ";
for (int j = 0; j < e[i].size(); j++){
cout << e[i][j].first << " ";
}
cout << endl;
}
*/
//cout << d[7] << d[2] << endl;
p = unos();
for (int i = 1; i <= p; i++){
poc[i] = unos();
kraj[i] = unos();
int lca_tr = lca(poc[i], kraj[i]);
//cout << lca_tr << endl;
if (poc[i] != kraj[i]){
if (max_lca[poc[i]] == 0 or d[lca_tr] < d[max_lca[poc[i]]]){
max_lca[poc[i]] = lca_tr;
ans[poc[i]] = i;
}
if (max_lca[kraj[i]] == 0 or d[lca_tr] < d[max_lca[kraj[i]]]){
max_lca[kraj[i]] = lca_tr;
ans[kraj[i]] = i;
}
}
}
brojac = 1;
for (int i = 1; i <= n; i++){
if (blok[i] == brojac){
dfs2(i, -1);
brojac++;
}
}
//cout << "aaa" << endl;
//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:73:2: warning: "/*" within comment [-Wcomment]
73 | /*
|
oneway.cpp: In function 'void dfs(int, int, int)':
oneway.cpp:92: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]
92 | for (int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:119: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]
119 | for (int i = 0; i < e[x].size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
