/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
if (fopen(filein.c_str(), "r")){
freopen(filein.c_str(), "r", stdin);
freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
freopen(fileerr.c_str(), "w", stderr);
#endif
}
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}
void Hollwo_Pelw();
signed main(){
#ifdef hollwo_pelw_local
FAST_IO("input.inp", "output.out", "error.err");
auto start = chrono::steady_clock::now();
#else
FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
#ifdef hollwo_pelw_local
auto end = chrono::steady_clock::now();
cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
return 0;
}
const int N = 1e5 + 5;
struct edge_t {
int u, v; char d = 'B';
} ed[N];
int n, m, q, tin[N], low[N], timer;
vector<pair<int, int>> adj[N];
int comp[N], compcnt;
vector<int> st;
void tarjan(int u, int p) {
tin[u] = low[u] = ++ timer;
st.push_back(u);
for (auto [v, i] : adj[u]) if (v != p) {
if (tin[v]) {
low[u] = min(low[u], tin[v]);
} else {
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
}
if (low[u] >= tin[u]) {
++ compcnt;
while (1) {
int v = st.back();
comp[v] = compcnt;
st.pop_back();
if (v == u) break ;
}
}
}
void __build_tree__() {
for (int i = 1; i <= n; i++)
adj[i].clear();
for (int i = 1; i <= m; i++) {
ed[i].u = comp[ed[i].u];
ed[i].v = comp[ed[i].v];
if (ed[i].u != ed[i].v) {
adj[ed[i].u].emplace_back(ed[i].v, i);
adj[ed[i].v].emplace_back(ed[i].u, i);
}
}
n = compcnt;
}
int dp[N];
void solve(int u, int p) {
for (auto [v, i] : adj[u]) if (v != p) {
solve(v, u);
if (dp[v] == 0)
ed[i].d = 'B';
else if (dp[v] < 0)
ed[i].d = u == ed[i].u ? 'R' : 'L';
else if (dp[v] > 0)
ed[i].d = u == ed[i].u ? 'L' : 'R';
dp[u] += dp[v];
}
}
void Hollwo_Pelw() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v, ed[i] = {u, v, 'B'};
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
for (int i = 1; i <= n; i++)
if (!tin[i]) tarjan(i, 0);
__build_tree__();
cin >> q;
for (int u, v; q --; )
cin >> u >> v, dp[comp[u]] ++, dp[comp[v]] --;
solve(1, 0);
for (int i = 1; i <= m; i++)
cout << ed[i].d;
}
Compilation message
oneway.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
oneway.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen(filein.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen(fileout.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
