#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
ll n, m, x,y, label = -1, q;
vector<ll> ans;
vector<pi> adj[100005];
vector<pi> treeadj[100005];
vector<pi> backadj[100005];
bool tree[100005];
vector<pi> edges;
vector<pi> city;
bool visited[100005];
ll depth[100005];
ll up[100005], down[100005], dp[100005];
ll bup[100005], bdown[100005], bdp[100005];
int lg(unsigned long long i) {
return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}
ll k, maxr;
vector<vector<pi > >rmq;
ll fa[100005];
vector<pi> arr;
void dfs1(ll p, ll node) // euler path
{
label++;
fa[node] = label;
arr.pb(mp(depth[node], node));
for (pi u: treeadj[node])
{
if (u.f==p) continue;
depth[u.f] = depth[node]+1;
dfs1(node, u.f);
label++;
arr.pb(mp(depth[node], node));
}
}
void initrmq()
{
maxr = arr.size();
k = lg(maxr);
rmq.assign(k+5, vector<pi> (maxr));
rmq[0] = arr;
for (ll i=1; i<=k; ++i)
{
for (ll j=0; j+ (1<<i) < maxr; ++j)
{
if (rmq[i-1][j].f < rmq[i-1][j + (1 << (i - 1))].f)
{
rmq[i][j] = rmq[i-1][j];
}
else
{
rmq[i][j] = rmq[i-1][j + (1 << (i - 1))];
}
}
}
}
ll lca(ll node1, ll node2)
{
ll l = fa[node1], r = fa[node2];
if (l>r) swap(l,r);
ll i = lg(r-l+1);
if (rmq[i][l] < rmq[i][r - (1 << i) + 1])
{
return rmq[i][l].s;
}
else
{
return rmq[i][r - (1 << i) + 1].s;
}
}
void dfs(ll p, ll from)
{
//show(from);
visited[from] = true;
for (pi u: adj[from])
{
if (u.f==p) continue;
if (!visited[u.f])
{
tree[u.s] = true;
treeadj[from].pb(u);
treeadj[u.f].pb(mp(from, u.s));
dfs(from, u.f);
}
}
}
void mark(ll p, ll node, ll label)
{
ll counter = 0;
ll bcounter = 0;
for (pi u: treeadj[node])
{
if (u.f==p) continue;
mark(node, u.f, label);
if (dp[u.f]>0 && bdp[u.f]==0) ans[u.s] = label;
counter+=dp[u.f];
bcounter+= bdp[u.f];
}
counter+=up[node] - down[node];
dp[node] = counter;
for (pi u: backadj[node])
{
//show(u.f);
if (lca(u.f, node)==node) bcounter--;
else bcounter++;
}
bdp[node] = bcounter;
//show3(node, dp[node], bdp[node]);
}
int main()
{
input(n); input(m);
ans.resize(m); edges.resize(m);
for (ll i=0; i<m; ++i)
{
cin >> x >> y;
x--;
y--;
adj[x].pb(mp(y, i));
adj[y].pb(mp(x, i));
edges[i] = mp(x,y);
}
dfs(-1, 0);
depth[0] = 0;
dfs1(-1, 0);
initrmq();
for (ll i=0; i<m; ++i)
{
if (!tree[i])
{
backadj[edges[i].f].pb(mp(edges[i].s, i));
backadj[edges[i].s].pb(mp(edges[i].f, i));
}
}
cin >> q;
city.resize(q);
for (ll i=0; i<q; ++i) {cin >> city[i].f >> city[i].s; city[i].f--; city[i].s--;}
memset(up, 0, sizeof up);memset(down, 0, sizeof down);memset(dp, 0, sizeof dp);
memset(up, 0, sizeof bup);memset(down, 0, sizeof bdown);memset(dp, 0, sizeof bdp);
for (ll i=0; i<q; ++i)
{
ll mid = lca(city[i].f, city[i].s);
if (mid==city[i].f) continue;
up[city[i].f]++;
down[mid]++;
}
//for (ll i=0;i<n; ++i) show3(i, up[i], down[i]);
//for (ll i=0; i<n; ++i) for (ll j=0; j<n; ++j) show3(i+1 ,j+1 , lca(i,j)+1);
mark(-1, 0, 1); // go up
memset(up, 0, sizeof up);memset(down, 0, sizeof down);memset(dp, 0, sizeof dp);
memset(up, 0, sizeof bup);memset(down, 0, sizeof bdown);memset(dp, 0, sizeof bdp);
for (ll i=0; i<q; ++i)
{
ll mid = lca(city[i].f, city[i].s);
if (mid==city[i].s) continue;
up[city[i].s]++;
down[mid]++;
}
mark(-1, 0, 2);// go down
for (ll i=0; i<m; ++i)
{
ll mid = lca(edges[i].f, edges[i].s);
if (ans[i]==0) cout << 'B';
else if ((ans[i]==1 && mid!=edges[i].f) || (ans[i]==2 && mid!=edges[i].s)) cout << 'R';
else cout << 'L';
}
cout << endl;
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
oneway.cpp:142:2: note: in expansion of macro 'input'
142 | input(n); input(m);
| ^~~~~
oneway.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
oneway.cpp:142:12: note: in expansion of macro 'input'
142 | input(n); input(m);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
13660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
13660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
13660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
