/**
* author: Haunted_Cpp
**/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
class Tarjan {
private:
vector<int> low, id;
int Time;
const int L;
set<pair<int, int>> bridge_count;
void dfs(int node, int p, const vector<vector<int>> &g) {
id[node] = low[node] = ++Time;
for (auto to : g[node]) {
if (to != p) {
if(id[to] == -1) dfs(to, node, g);
low[node] = min(low[node], low[to]);
if (id[node] < low[to]) {
bridge_count.insert({min(node, to), max(node, to)});
}
}
}
}
public:
Tarjan(const vector<vector<int>> &g) : L((int)g.size()){
low.clear();
id.clear();
Time = 0;
find_bridge(g);
}
void find_bridge(const vector<vector<int>> &g) {
low = vector<int>(L, -1);
id = vector<int>(L, -1);
for (int i = 0; i < L; i++) {
if (id[i] == -1) {
dfs(i, -1, g);
}
}
}
bool is_bridge(int st, int et) {
return bridge_count.find({min(st, et), max(st, et)}) != bridge_count.end();
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
vector<pair<int, int>> edge(m);
for (int i = 0; i < m; i++) {
int st, et;
cin >> st >> et;
--st; --et;
edge[i] = {st, et};
g[st].emplace_back(et);
g[et].emplace_back(st);
}
Tarjan solve(g);
string ans = string(m, 'B');
for (int i = 0; i < m; i++) {
if(solve.is_bridge(edge[i].first, edge[i].second) == true) {
ans[i] = '-';
}
}
set<pair<int, int>> dir;
auto Bfs = [&](int source, int destination) {
queue<int> q;
q.push(source);
vector<int> par(n, -1);
vector<bool> vis(n, false);
vis[source] = true;
while(!q.empty()) {
int node = q.front();
q.pop();
for (auto to : g[node]) {
if (!vis[to]) {
vis[to] = true;
q.push(to);
par[to] = node;
}
}
}
//~ debug("SOURCE: ", source + 1);
int current_node = destination;
while(current_node != -1) {
int was = current_node;
current_node = par[current_node];
if (current_node == -1) break;
//~ debug(current_node + 1, was + 1);
dir.insert({current_node, was});
}
};
int q;
cin >> q;
while(q--) {
int st, et;
cin >> st >> et;
--st; --et;
Bfs(st, et);
}
for (int i = 0; i < m; i++) {
if(ans[i] == '-') {
if(dir.find({edge[i].first, edge[i].second}) != dir.end()) {
ans[i] = 'R';
assert(dir.find({edge[i].second, edge[i].first}) == dir.end());
} else {
ans[i] = 'L';
assert(dir.find({edge[i].first, edge[i].second}) == dir.end());
}
}
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
