#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 20;
char resp[MAXN];
int low[MAXN];
vector <int> grafo[MAXN], id[MAXN];
pair <int, int> ar[MAXN];
int marc[MAXN], prof[MAXN], marc3[MAXN];
int t;
void dfs(int v, int p) {
t++;
prof[v] = t;
low[v] = prof[v];
marc[v] = 1;
int idp = 0;
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
int id1 = id[v][i];
if(id1 == p) {
//idp = id[v][i];
continue;
}
if(marc[viz] == 0) {
//prof[viz] = prof[v] + 1;
dfs(viz, id1);
low[v] = min(low[v], low[viz]);
if(low[viz] > prof[v]) {
marc3[id[v][i]] = 1;
//printf("%d %d %d\n", id[v][i], v, viz);
}
}
else {
low[v] = min(low[v], prof[viz]);
}
/*else {
printf("N %d %d %d %d\n", v, viz, low[viz], prof[v]);
}*/
}
//printf("%d %d %d %d\n", v, low[v], prof[v], idp);
}
int pai[MAXN], tam[MAXN];
int find(int v) {
//printf("%d\n", v);
if(pai[v] == v) return v;
return pai[v] = find(pai[v]);
}
void une(int a, int b) {
a = find(a); b = find(b);
if(a == b) return;
if(tam[a] < tam[b]) {
pai[a] = b;
tam[b] += tam[a];
}
else {
pai[b] = a;
tam[a] += tam[b];
}
}
vector <int> grafo2[MAXN], id2[MAXN];
int dp[MAXN][MAXK];
void dfs1(int v, int p) {
//printf("%d\n", v);
dp[v][0] = p;
for(int i = 0; i < grafo2[v].size(); i++) {
int viz = grafo2[v][i];
if(viz == p) continue;
prof[viz] = prof[v] + 1;
dfs1(viz, v);
}
}
int lca(int a, int b) {
if(prof[a] > prof[b]) swap(a, b);
int d = prof[b] - prof[a];
for(int i = 0; i < MAXK; i++) {
if(d & (1 << i)) {
b = dp[b][i];
}
}
if(a == b) return a;
for(int i = MAXK - 1; i >= 0; i--) {
if(dp[a][i] != dp[b][i]) {
a = dp[a][i]; b = dp[b][i];
}
}
return dp[b][0];
}
int dec1[MAXN], sub[MAXN];
void dfs2(int v, int p) {
int idp = 0;
for(int i = 0; i < grafo2[v].size(); i++) {
int viz = grafo2[v][i];
if(viz == p) {
idp = id2[v][i];
continue;
}
dfs2(viz, v);
dec1[v] += dec1[viz]; sub[v] += sub[viz];
}
int s, c;
if(dec1[v] > 0) {
c = v; s = p;
//printf("%d %d\n", c, s);
int a = find(ar[idp].first), b = find(ar[idp].second);
if(a == s) {
resp[idp] = 'R';
}
else {
resp[idp] = 'L';
}
}
else if(sub[v] > 0){
c = p; s = v;
//printf("%d %d\n", c, s);
int a = find(ar[idp].first), b = find(ar[idp].second);
if(a == s) {
resp[idp] = 'R';
}
else {
resp[idp] = 'L';
}
}
else {
resp[idp] = 'B';
}
}
int dfs4(int v, int p ,int k) {
//printf("%d\n", v);
int tot = 1;
marc[v] = 1;
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i], id1 = id[v][i];
if(id1 == k) continue;
if(viz == p) continue;
if(marc[viz] == 1) continue;
tot += dfs4(viz, v, k);
}
return tot;
}
void dscb(int n, int m) {
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) marc[j] = 0;
if(dfs4(1, 1, i) == n) marc3[i] = 0;
else marc3[i] = 1;
//printf("oi\n");
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
grafo[a].push_back(b); grafo[b].push_back(a);
id[a].push_back(i + 1); id[b].push_back(i + 1);
ar[i + 1] = make_pair(a, b);
}
/*for(int i = 1; i <= m; i++) if(ar[i].first < ar[i].first) swap(ar[i].first, ar[i].second);
sort(ar + 1, ar + m + 1);
for(int i = 1; i < m; i++) {
if(ar[i].first == ar[i + 1].first && ar[i].second == ar[i + 1].second) {
while(true) {
}
}
}*/
//dfs(1, 1);
dscb(n, m);
for(int i = 1; i <= n; i++) {
pai[i] = i; tam[i] = 1;
}
for(int i = 1; i <= m; i++) {
if(marc3[i] == 0 || marc3[i] == 2) {
//printf("%d\n", i);
resp[i] = 'B';
une(ar[i].first, ar[i].second);
}
}
for(int i = 1; i <= m; i++) {
if(marc3[i] == 1) {
int a = find(ar[i].first), b = find(ar[i].second);
//printf("%d %d\n", ar[i].first, ar[i].second);
grafo2[a].push_back(b); grafo2[b].push_back(a);
id2[a].push_back(i); id2[b].push_back(i);
//printf("%d %d %d\n", i, a, b);
}
}
//printf("oi\n");
int ini = find(1);
prof[ini] = 0;
//printf("oi\n");
dfs1(ini, ini);
//printf("oi\n");
for(int i = 1; i < MAXK; i++) {
for(int j = 1; j <= n; j++) {
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
//printf("oi\n");
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++) {
int a, b;
scanf("%d %d", &a, &b);
a = find(a); b = find(b);
if(a == b) continue;
int c = lca(a, b);
sub[c]--; dec1[c]--;
sub[a]++; dec1[b]++;
}
dfs2(ini, ini);
for(int i = 1; i <= m; i++) {
printf("%c", resp[i]);
}
printf("\n");
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i = 0; i < grafo[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
oneway.cpp:15:6: warning: unused variable 'idp' [-Wunused-variable]
15 | int idp = 0;
| ^~~
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < grafo2[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < grafo2[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
oneway.cpp:103:32: warning: unused variable 'b' [-Wunused-variable]
103 | int a = find(ar[idp].first), b = find(ar[idp].second);
| ^
oneway.cpp:114:32: warning: unused variable 'b' [-Wunused-variable]
114 | int a = find(ar[idp].first), b = find(ar[idp].second);
| ^
oneway.cpp:99:9: warning: variable 'c' set but not used [-Wunused-but-set-variable]
99 | int s, c;
| ^
oneway.cpp: In function 'int dfs4(int, int, int)':
oneway.cpp:130:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for(int i = 0; i < grafo[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
149 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
152 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:200:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
200 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
oneway.cpp:203:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
203 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
181 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
