#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int t, n, m, q, put1, put2;
pair<int, int> edg[100002];
int spoji[100002];
vector< pair<int, int> > v[100002];
vector< pair<int, int> > vnovi[100002];
vector< pair<int, int> > gore[100002];
int discovery[100002];
int min_gore[100002];
int trendisc = 0;
//vector< pair<int, int> > sol;
void dfs(int cvor, int prt) {
trendisc ++;
discovery[cvor] = trendisc;
for (int i = 0; i < v[cvor].size(); i++) {
int sus = v[cvor][i].X;
if (sus != prt) {
if (discovery[sus] == 0) {
vnovi[cvor].push_back({sus, v[cvor][i].Y});
dfs(sus, cvor);
}
else {
gore[cvor].push_back({sus, v[cvor][i].Y});
}
}
}
}
int set_gore(int cvor, int prt) {
min_gore[cvor] = discovery[cvor];
for (int i = 0; i < gore[cvor].size(); i++) {
min_gore[cvor] = min(min_gore[cvor], discovery[ gore[cvor][i].X ]);
}
for (int i = 0; i < vnovi[cvor].size(); i++) {
int sus = vnovi[cvor][i].X;
if (sus != prt) {
min_gore[cvor] = min(min_gore[cvor], set_gore(sus, cvor));
}
}
for (int i = 0; i < vnovi[cvor].size(); i++) {
int sus = vnovi[cvor][i].X;
if (sus != prt && discovery[cvor] < min_gore[sus]) {
spoji[ vnovi[cvor][i].Y ] = -1;
}
}
return min_gore[cvor];
}
int rod[100002];
vector< pair<int, int> > graf[100002];
int find(int cvor) {
if (cvor == rod[cvor]) return cvor;
return rod[cvor] = find(rod[cvor]);
}
void unija(int cvor1, int cvor2) {
cvor1 = find(cvor1);
cvor2 = find(cvor2);
if (cvor1 == cvor2) return;
if (rand() % 2 == 0) {
rod[cvor1] = cvor2;
}
else {
rod[cvor2] = cvor1;
}
}
string sol = "";
int dub[100002];
int lift[25][100002];
void postavi(int cvor, int prt) {
for (int i = 0; i < graf[cvor].size(); i++) {
int sus = graf[cvor][i].X;
if (sus != prt) {
lift[0][sus] = cvor;
//cout << sus << " -> " << cvor << endl;
dub[sus] = dub[cvor]+1;
postavi(sus, cvor);
}
}
}
int prefg[100002];
int prefd[100002];
int findlca(int cvor1, int cvor2) {
if (dub[cvor1] < dub[cvor2]) swap(cvor1, cvor2);
for (int i = 19; i >= 0; i--) {
if (dub[ lift[i][cvor1] ] >= dub[cvor2]) {
cvor1 = lift[i][cvor1];
}
}
if (cvor1 == cvor2) return cvor1;
for (int i = 19; i >= 0; i--) {
if (lift[i][cvor1] != lift[i][cvor2]) {
cvor1 = lift[i][cvor1];
cvor2 = lift[i][cvor2];
}
}
return lift[0][cvor1];
}
void rek(int cvor, int prt) {
for (int i = 0; i < graf[cvor].size(); i++) {
int sus = graf[cvor][i].X;
if (prt != sus) {
rek(sus, cvor);
if (prefg[sus] > 0) {
sol[ graf[cvor][i].Y ] = 'X';
}
if (prefd[sus] > 0) {
sol[ graf[cvor][i].Y ] = 'Y';
}
prefg[cvor] += prefg[sus];
prefd[cvor] += prefd[sus];
}
}
}
int main () {
srand(time(NULL));
cin >> n >> m;
memset(dub, -1, sizeof dub);
for (int i = 1; i <= n; i++) {
rod[i] = i;
}
for (int i = 0; i < m; i++) {
sol.push_back('B');
cin >> edg[i].X >> edg[i].Y;
v[edg[i].X].push_back({edg[i].Y, i});
v[edg[i].Y].push_back({edg[i].X, i});
}
dfs(1, 0);
set_gore(1, 0);
for (int i = 0; i < m; i++) {
if (spoji[i] != -1) {
unija(edg[i].X, edg[i].Y);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < v[i].size(); j++) {
int tr1 = find(i);
int tr2 = find(v[i][j].X);
if (tr1 != tr2) {
graf[tr1].push_back({tr2, v[i][j].Y});
//graf[tr2].push_back({tr1, v[i][j].Y});
}
}
}
int glavni = 0;
for (int i = 1; i <= n; i++) {
if (graf[i].size() > 0) {
glavni = i;
break;
}
}
postavi(glavni, 0);
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
lift[i][j] = lift[i-1][ lift[i-1][j] ];
}
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> put1 >> put2;
put1 = find(put1);
put2 = find(put2);
prefg[put1] ++;
prefd[put2] ++;
int lca = findlca(put1, put2);
prefg[lca] --;
prefd[lca] --;
}
rek(glavni, 0);
/*for (int i = 1; i <= n; i++) {
cout << i << ": " << prefg[i] << " " << prefd[i] << endl;
}*/
for (int i = 0; i < m; i++) {
if (sol[i] != 'B') {
if (dub[ edg[i].X ] < dub[ edg[i].Y ]) {
if (sol[i] == 'X') sol[i] = 'L';
else sol[i] = 'R';
}
else {
if (sol[i] == 'X') sol[i] = 'R';
else sol[i] = 'L';
}
}
}
cout << sol;
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v[cvor].size(); i++) {
~~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'int set_gore(int, int)':
oneway.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < gore[cvor].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
oneway.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vnovi[cvor].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vnovi[cvor].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void postavi(int, int)':
oneway.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graf[cvor].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void rek(int, int)':
oneway.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < graf[cvor].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:166:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v[i].size(); j++) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
10232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
