#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], visited2[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
{
visited2[node] = true;
label++;
fa[node] = label;
arr.pb(mp(depth[node], node));
for (pi u: treeadj[node])
{
if (u.f==p || visited2[u.f]) 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)
{
show2(p, 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)
{
visited[node] = true;
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])
{
if (u.f==node) continue;
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--;
assert(x!=y);
adj[x].pb(mp(y, i));
adj[y].pb(mp(x, i));
edges[i] = mp(x,y);
}
for (ll i=0; i<m; ++i) {tree[i] = 0, ans[i] = 0;}
for (ll i=0; i<n; ++i) if (!visited[i]) dfs(-1, i);
label= -1;
depth[0] = 0;
for (ll i=0; i<n; ++i) if (!visited2[i])dfs1(-1, i);
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));
show2(edges[i].s, edges[i].f);
}
}
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--;}
for (ll i=0; i<n; i++) {up[i] = 0, down[i] = 0, dp[i] = 0, bup[i] = 0, bdown[i] = 0, bdp[i]= 0; visited[i] = false;}
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);
for (ll i=0; i<n; ++i) if (!visited[i]) mark(-1, i, 1); // go up
for (ll i=0; i<n; i++) {up[i] = 0, down[i] = 0, dp[i] = 0, bup[i] = 0, bdown[i] = 0, bdp[i]= 0;visited[i] = false;}
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]++;
}
for (ll i=0; i<n; ++i) if (!visited[i]) mark(-1, i, 2);// go down
for (ll i=0; i<m; ++i)
{
ll mid = lca(edges[i].f, edges[i].s);
if (!tree[i] || 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:144:2: note: in expansion of macro 'input'
144 | 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:144:12: note: in expansion of macro 'input'
144 | input(n); input(m);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
11 ms |
13660 KB |
Output is correct |
| 3 |
Execution timed out |
3044 ms |
23480 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
11 ms |
13660 KB |
Output is correct |
| 3 |
Execution timed out |
3044 ms |
23480 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
13656 KB |
Output is correct |
| 2 |
Correct |
11 ms |
13660 KB |
Output is correct |
| 3 |
Execution timed out |
3044 ms |
23480 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
