#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
enum {IN, OUT};
enum {UP = 1, DOWN = 2};
class s2l
{
private:
set<pii> s[2];
public:
size_t size()
{
return s[0].size() + s[1].size();
}
void insert(int v, int u, bool dir)
{
auto it = s[!dir].find({u, v});
if (it != s[!dir].end())
s[!dir].erase(it);
else
s[dir].insert({v, u});
}
void merge(s2l *x)
{
if (size() > x->size()) {
s[IN].swap(x->s[IN]);
s[OUT].swap(x->s[OUT]);
}
for (auto [v, u] : x->s[IN])
insert(v, u, IN);
for (auto [u, v] : x->s[OUT])
insert(v, u, OUT);
delete(x);
}
int get()
{
return (DOWN & -s[OUT].empty()) | (UP & -s[IN].empty());
}
};
vector<pii> Ao[N];
vector<pii> A2[N];
int col2[N];
bool ncut[N];
int h[N];
int find_ncut(int v, int p, int h)
{
static bool vis[N];
::h[v] = h;
int mn = h;
vis[v] = 1;
for (auto [u, ei] : Ao[v]) {
if (ei == p)
continue;
if (vis[u]) {
mn = min(mn, ::h[u]);
ncut[ei] = 1;
} else {
int x = find_ncut(u, ei, h+1);
if (x <= h)
ncut[ei] = 1;
mn = min(mn, x);
}
}
return mn;
}
void make_col2(int v, int col)
{
col2[v] = col;
for (auto [u, ei] : Ao[v]) {
if (ncut[ei] && col2[u] == -1)
make_col2(u, col);
}
}
vector<pii> Eo;
vector<pii> req2[N];
void make_A2()
{
Loop (i,0,Eo.size()) {
auto [v, u] = Eo[i];
v = col2[v];
u = col2[u];
if (v != u) {
A2[v].push_back({u, i});
A2[u].push_back({v, i});
}
}
}
void read_and_make_req2()
{
int p;
cin >> p;
Loop (i,0,p) {
int v, u;
cin >> v >> u;
--v; --u;
v = col2[v]; u = col2[u];
if (v != u) {
req2[v].push_back({u, OUT});
req2[u].push_back({v, IN});
}
}
}
int ans2[N];
s2l *main_dfs(int v, int p)
{
s2l *obj = new s2l;
for (auto [u, dir] : req2[v])
obj->insert(v, u, dir);
for (auto [u, ei] : A2[v]) {
if (ei == p)
continue;
obj->merge(main_dfs(u, ei));
}
if (p != -1)
ans2[p] = obj->get();
return obj;
}
char get_char(int ei)
{
auto [v, u] = Eo[ei];
switch (ans2[ei]) {
case UP|DOWN: return 'B';
case UP : return h[v] < h[u]? 'L': 'R';
case DOWN: return h[v] > h[u]? 'L': 'R';
default : return 'N';
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int n, m;
cin >> n >> m;
Loop (i,0,m) {
int v, u;
cin >> v >> u;
--v; --u;
Ao[v].push_back({u,i});
Ao[u].push_back({v,i});
Eo.push_back({v, u});
}
find_ncut(0, -1, 0);
//Loop (i,0,m) cout << ncut[i] << ' '; cout << '\n';
int n2 = 0;
memset(col2, -1, sizeof(col2));
Loop (i,0,n) {
if (col2[i] == -1)
make_col2(i, n2++);
}
//Loop (i,0,n) cout << col2[i] << ' '; cout << '\n';
make_A2();
read_and_make_req2();
delete(main_dfs(0, -1));
Loop (i,0,m) {
auto [v, u] = Eo[i];
cout << (col2[v] == col2[u]? 'B': get_char(i));
}
cout << '\n';
}
Compilation message
oneway.cpp: In function 'void make_A2()':
oneway.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
| ^
oneway.cpp:91:2: note: in expansion of macro 'Loop'
91 | Loop (i,0,Eo.size()) {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
7764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
