#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#pragma warning (disable: 4996)
int N, M, A[1 << 18], B[1 << 18], pre[1 << 18], low[1 << 18], col[1 << 18], dp[1 << 17][22], dist[1 << 17], cnt[1 << 17], state[1 << 17], cnts;
map<pair<int, int>, int>Map, Map2;
vector<int>X[1 << 17], Y[1 << 17], Z[1 << 17];
bool bridge[1 << 18], dir[1 << 18], used[1 << 18];
void dfs1(int pos, int prev_) {
cnts++; pre[pos] = cnts; low[pos] = cnts;
for (int i = 0; i < X[pos].size(); i++) {
if (pre[X[pos][i]] >= 1) {
if (X[pos][i] != prev_) low[pos] = min(low[pos], low[X[pos][i]]);
continue;
}
else {
dfs1(X[pos][i], pos);
low[pos] = min(low[pos], low[X[pos][i]]);
if (low[X[pos][i]] == pre[X[pos][i]]) {
bridge[abs(Map[make_pair(pos, X[pos][i])])] = true;
}
}
}
}
void dfs2(int pos) {
if (col[pos] >= 1) return;
col[pos] = cnts;
for (int i = 0; i < Y[pos].size(); i++) {
dfs2(Y[pos][i]);
}
}
void dfs3(int pos, int dep) {
used[pos] = true; dist[pos] = dep;
for (int i = 0; i < Z[pos].size(); i++) {
if (used[Z[pos][i]] == true) continue;
dp[Z[pos][i]][0] = pos;
dfs3(Z[pos][i], dep + 1);
}
}
int prevs(int pos, int x) {
for (int i = 21; i >= 0; i--) {
if (x >= (1 << i)) { pos = dp[pos][i]; x -= (1 << i); }
}
return pos;
}
int lca(int u, int v) {
if (dist[u] > dist[v]) swap(u, v);
v = prevs(v, dist[v] - dist[u]);
if (u == v) return u;
for (int i = 21; i >= 0; i--) {
if (dp[u][i] != dp[v][i]) {
u = dp[u][i];
v = dp[v][i];
}
}
return dp[u][0];
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= M; i++) {
scanf("%d%d", &A[i], &B[i]);
X[A[i]].push_back(B[i]); Map[make_pair(A[i], B[i])] = i;
X[B[i]].push_back(A[i]); Map[make_pair(B[i], A[i])] = -i;
}
for (int i = 1; i <= N; i++) { pre[i] = 0; low[i] = (1 << 30); }
dfs1(1, -1);
for (int i = 1; i <= M; i++) {
if (bridge[i] == true) continue;
Y[A[i]].push_back(B[i]);
Y[B[i]].push_back(A[i]);
}
cnts = 0;
for (int i = 1; i <= N; i++) {
if (col[i] >= 1) continue;
cnts++; dfs2(i);
}
for (int i = 1; i <= M; i++) {
if (bridge[i] == false) continue;
Z[col[A[i]]].push_back(col[B[i]]); Map2[make_pair(col[A[i]], col[B[i]])] = i;
Z[col[B[i]]].push_back(col[A[i]]); Map2[make_pair(col[B[i]], col[A[i]])] = -i;
}
dfs3(1, 0);
for (int i = 0; i < 21; i++) {
for (int j = 1; j <= cnts; j++) dp[j][i + 1] = dp[dp[j][i]][i];
}
int Q; scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
int ca, cb; scanf("%d%d", &ca, &cb);
ca = col[ca]; cb = col[cb];
int v = lca(ca, cb);
cnt[ca]++; cnt[cb]--;
}
vector<pair<int, int>>I;
for (int i = 1; i <= cnts; i++) I.push_back(make_pair(dist[i], i));
sort(I.begin(), I.end());
for (int i = I.size() - 1; i >= 1; i--) {
cnt[dp[I[i].second][0]] += cnt[I[i].second];
}
for (int i = 2; i <= cnts; i++) {
if (cnt[i] == 0) continue;
bool p1 = false; if (Map2[make_pair(i, dp[i][0])] <= -1) p1 = true;
bool p2 = false; if (cnt[i] <= -1) p2 = true;
if ((p1^p2) == false) state[abs(Map2[make_pair(i, dp[i][0])])] = 1;
else state[abs(Map2[make_pair(i,dp[i][0])])] = 2;
}
for (int i = 1; i <= M; i++) {
if (state[i] == 0) printf("B");
if (state[i] == 1) printf("L");
if (state[i] == 2) printf("R");
}
printf("\n");
return 0;
}
Compilation message
oneway.cpp:6:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Y[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < Z[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:102:7: warning: unused variable 'v' [-Wunused-variable]
int v = lca(ca, cb);
^
oneway.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int Q; scanf("%d", &Q);
~~~~~^~~~~~~~~~
oneway.cpp:100:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int ca, cb; scanf("%d%d", &ca, &cb);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
