#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
out << "[";
for (int i = 0; i < (int)vec.size(); ++i) {
out << vec[i];
if (i + 1 < (int)vec.size())
out << ", ";
}
return out << "]";
}
} // namespace std
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << H;
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const int MAXN = 1e5;
struct UnionFind {
vector<int> id;
UnionFind() {}
UnionFind(int N) { id.assign(N, -1); }
int find(int u) {
if (id[u] < 0)
return u;
return id[u] = find(id[u]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v)
return false;
if (id[u] > id[v])
swap(u, v);
id[u] += id[v];
id[v] = u;
return true;
}
};
vector<pair<int, int>> adj[MAXN];
vector<pair<int, int>> edges;
vector<int> num, st;
int Time;
vector<int> bridges;
bool isBridge[MAXN];
int dfs(int at, int par) {
int me = num[at] = ++Time, e, y, top = me;
for (auto pa : adj[at])
if (pa.second != par) {
tie(y, e) = pa;
if (num[y])
top = min(top, num[y]);
else {
int up = dfs(y, e);
top = min(top, up);
if (up == me) {
} else if (up < me) {
} else {
bridges.push_back(e);
isBridge[e] = true;
}
}
}
return top;
}
void bicomps() {
num.assign(edges.size(), 0);
for (int i = 0; i < (int)edges.size(); ++i)
if (!num[i])
dfs(i, -1);
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int nbSommet, nbAretes, nbRequetes;
cin >> nbSommet >> nbAretes;
edges.resize(nbAretes);
for (int i = 0; i < nbAretes; ++i) {
auto &[u, v] = edges[i];
cin >> u >> v;
--u, --v;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
cin >> nbRequetes;
vector<pair<int, int>> queries(nbRequetes);
for (auto &[u, v] : queries) {
cin >> u >> v;
--u, --v;
}
bicomps();
UnionFind dsu(nbSommet);
for (int i = 0; i < nbAretes; ++i)
if (!isBridge[i])
dsu.merge(edges[i].first, edges[i].second);
vector<int> roots;
for (int u = 0; u < nbSommet; ++u)
if (dsu.find(u) == u)
roots.push_back(u);
auto getId = [&](int u) {
return lower_bound(roots.begin(), roots.end(), dsu.find(u)) - roots.begin();
};
for (int u = 0; u < nbSommet; ++u)
adj[u].clear();
for (int iArete = 0; iArete < nbAretes; ++iArete) {
if (isBridge[iArete]) {
auto [u, v] = edges[iArete];
u = getId(u);
v = getId(v);
if (u == v)
continue;
adj[u].emplace_back(v, iArete);
adj[v].emplace_back(u, iArete);
}
}
int nbRoots = roots.size();
vector<int> cntDeb(nbRoots), cntFin(nbRoots);
for (auto [u, v] : queries) {
u = getId(u);
v = getId(v);
if (u == v)
continue;
cntDeb[u]++;
cntFin[v]++;
}
vector<int> side(nbAretes);
vector<bool> seen(nbRoots);
auto dfsBridge = [&](auto rec, int u, int p) -> void {
seen[u] = true;
for (auto [v, id] : adj[u])
if (v != p) {
rec(rec, v, u);
cntDeb[u] += cntDeb[v];
cntFin[u] += cntFin[v];
if (cntDeb[v] > cntFin[v]) {
side[id] = edges[id].first == u ? -1 : 1;
}
if (cntFin[v] > cntDeb[v])
side[id] = edges[id].first == u ? 1 : -1;
}
};
for (int u = 0; u < nbRoots; ++u)
if (!seen[u])
dfsBridge(dfsBridge, u, u);
for (int x : side) {
if (x == 0)
cout << 'B';
else if (x == -1)
cout << 'L';
else
cout << 'R';
}
cout << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
