#include <bits/stdc++.h>
using namespace std;
#define INPFILE "CEOI17_oneway.inp"
#define OUTFILE "CEOI17_oneway.out"
template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
if (x < y) { x = y; return true; }
return false;
}
class Tree {
private:
int n;
vector<vector<tuple<int, int, bool>>> adj;
vector<pair<int, int>> par;
vector<pair<int, bool>> reqs;
// void dfs(int u = 0, int p = -1) {
// for (const auto &e : adj[u]) {
// int v = e.first;
// if (v == p) {
// par[v] = e;
// continue;
// }
// dfs(v, u);
// }
// }
//
//
bool dfs_dir(int u, int y, int p = -1) {
// cerr << "dfs_dir " << u << " " << y << endl;
if (u == y)
return true;
for (const auto &e : adj[u]) {
int v, i; bool dir;
tie(v, i, dir) = e;
if (v == p)
continue;
if (dfs_dir(v, y, u)) {
reqs.emplace_back(i, dir);
return true;
}
}
return false;
}
public:
Tree() {}
Tree(int n): n(n) {
adj.assign(n, vector<tuple<int, int, bool>>());
}
inline void add_edge(int u, int v, int i) {
adj[u].emplace_back(v, i, true);
adj[v].emplace_back(u, i, false);
}
void traverse() {
// par.assign(n, make_pair(-1, -1));
// dfs();
}
inline void set_dir(int x, int y) {
dfs_dir(x, y);
}
template <class Func>
inline void FOR_REQS(Func f) {
for (const auto &e : reqs)
f(e.first, e.second);
}
};
const int MAX = 1e5 + 7;
int N, M, P;
vector<pair<int, int>> edges;
vector<int> adj[MAX];
vector<pair<int, int>> dirs;
inline int OTHER_NODE(int i, int u) {
return edges[i].first ^ edges[i].second ^ u;
}
void input() {
cin >> N >> M;
for (int t = M; t--; ) {
int u, v; cin >> u >> v;
adj[u].push_back(edges.size());
adj[v].push_back(edges.size());
edges.emplace_back(u, v);
}
cin >> P;
for (int t = P; t--; ) {
int x, y; cin >> x >> y;
dirs.emplace_back(x, y);
}
}
int COUNTER, tin[MAX], low[MAX], root[MAX], comp[MAX];
int COUNT_BCCS;
stack<int> st;
bool on_stack[MAX];
void dfs(int u, int pi = -1) {
tin[u] = low[u] = ++COUNTER;
st.push(u);
on_stack[u] = true;
for (int i : adj[u]) if (i != pi) {
int v = OTHER_NODE(i, u);
if (tin[v] == 0) {
dfs(v, u);
minimise(low[u], low[v]);
}
else
minimise(low[u], tin[v]);
}
if (low[u] == tin[u]) {
while (true) {
int v = st.top(); st.pop();
on_stack[v] = false;
root[v] = u;
comp[v] = COUNT_BCCS;
if (v == u)
break;
}
COUNT_BCCS++;
}
}
Tree tree;
void init() {
COUNTER = COUNT_BCCS = 0;
memset(tin, 0, sizeof tin);
for (int u = 1; u <= N; u++) if (tin[u] == 0)
dfs(u);
tree = Tree(COUNT_BCCS);
for (int i = 0; i < M; i++) {
int u, v;
tie(u, v) = edges[i];
if (comp[u] == comp[v])
continue;
tree.add_edge(comp[u], comp[v], i);
}
tree.traverse();
}
void solve() {
for (const auto &p : dirs) {
int x, y;
tie(x, y) = p;
tree.set_dir(comp[x], comp[y]);
}
string ans(M, 'B');
tree.FOR_REQS([&](int i, bool dir) {
ans[i] = (dir ? 'R' : 'L');
});
cout << ans;
}
int main(void) {
if (fopen(INPFILE, "r")) {
freopen(INPFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
}
input();
init();
solve();
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | freopen(INPFILE, "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | freopen(OUTFILE, "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
