This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
int U[MAXN], V[MAXN], ans[MAXN], br[MAXN], id[MAXN];
bool vis[MAXN], mrk[MAXN];
int low[MAXN], disc[MAXN];
int npar[20][MAXN], depth[MAXN], f[MAXN];
int qry[MAXN][3];
vii adj[MAXN], tree[MAXN];
int t = 0;
void dfs(int u, int p)
{
low[u] = disc[u] = t++;
vis[u] = 1;
for (pii nx: adj[u])
{
int v = nx.fi;
if (nx.se == p)
continue;
if (!vis[v])
{
dfs(v, nx.se);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u])
br[nx.se] = 1;
}
else
low[u] = min(low[u], disc[v]);
}
}
int cur = 0;
void tr(int u)
{
deque<int> pq;
pq.pb(u);
vis[u] = 1;
int cmp = cur;
id[u] = cmp;
while (!pq.empty())
{
int ur = pq.front(); pq.pop_front();
for (pii nx: adj[ur])
{
int v = nx.fi;
if (vis[v])
continue;
if (br[nx.se])
{
cur++;
tree[cur].pb({cmp, nx.se});
tree[cmp].pb({cur, nx.se});
tr(v);
}
else
{
pq.pb(v);
id[v] = cmp;
vis[v] = 1;
}
}
}
}
void dfs2(int u, int p, int d)
{
depth[u] = d;
for (pii nx: tree[u])
{
int v = nx.fi;
if (v != p)
{
f[v] = nx.se;
dfs2(v, u, d + 1);
npar[0][v] = u;
}
}
}
int lca(int u, int v)
{
if (depth[u] > depth[v])
swap(u, v);
int d = depth[v] - depth[u];
for (int i = 16; i >= 0; i--)
if ((d >> i) & 1)
v = npar[i][v];
if (u == v)
return v;
for (int i = 16; i >= 0; i--)
if (npar[i][u] != npar[i][v])
u = npar[i][u], v = npar[i][v];
return npar[0][u];
}
int main()
{
int n, m, p;
ni(n), ni(m);
for (int i = 0; i < m; i++)
{
ni(U[i]), ni(V[i]);
U[i]--, V[i]--;
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i});
}
int c = 0;
vi tmp, tmp2;
for (int i = 0; i < n; i++)
if (!vis[i])
dfs(i, -1), c++, tmp.pb(i);
memset(vis, 0, sizeof vis);
for (int i = 0; i < c; i++)
tmp2.pb(cur), tr(tmp[i]), cur++;
for (int i= 0; i < c; i++)
dfs2(tmp2[i], -1, 0);
for (int i = 1; i < 17; i++)
for (int j = 0; j < cur; j++)
npar[i][j] = npar[i - 1][npar[i - 1][j]];
vii arr;
ni(p);
for (int i = 0; i < p; i++)
{
int u, v;
ni(u), ni(v);
u--, v--;
u = id[u], v = id[v];
if (u == v)
continue;
int l = lca(u, v);
arr.pb({depth[l], i});
qry[i][0] = u, qry[i][1] = v, qry[i][2] = l;
}
sort(arr.begin(), arr.end());
for (pii nx: arr)
{
int u = qry[nx.se][0], v = qry[nx.se][1], l = qry[nx.se][2];
int x = u;
while (x != l)
{
if (mrk[f[x]])
break;
mrk[f[x]] = 1;
if (id[U[f[x]]] == x)
ans[f[x]] = 2;
else
ans[f[x]] = 1;
x = npar[0][x];
}
x = v;
while (x != l)
{
if (mrk[f[x]])
break;
mrk[f[x]] = 1;
if (id[U[f[x]]] == x)
ans[f[x]] = 1;
else
ans[f[x]] = 2;
x = npar[0][x];
}
}
for (int i = 0; i < m; i++)
if (ans[i] == 0)
printf("B");
else if (ans[i] == 1)
printf("L");
else
printf("R");
enl;
return 0;
}
Compilation message (stderr)
oneway.cpp: In function 'int main()':
oneway.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ni(n), ni(m);
^
oneway.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
oneway.cpp:126:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ni(U[i]), ni(V[i]);
^
oneway.cpp:126:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
oneway.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define ni(n) scanf("%d", &(n))
~~~~~^~~~~~~~~~~~
oneway.cpp:145:5: note: in expansion of macro 'ni'
ni(p);
^~
oneway.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ni(u), ni(v);
^
oneway.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |