#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005, LG = 18;
int n, m, q, from[N], to[N], M[N], H[N], Mn[N];
int cp, Hc[N], C[N], P[N][LG], up[N], dn[N];
int qa[N], qb[N];
char R[N];
vector < int > Adj[N], Ad[N];
void DFS(int v, int p)
{
Mn[v] = H[v]; M[v] = 1;
for (int &id : Adj[v])
{
if (id == p)
continue;
int u = from[id] ^ to[id] ^ v;
if (M[u] == 2)
continue;
else if (M[u] == 1)
Mn[v] = min(Mn[v], H[u]);
else
{
H[u] = H[v] + 1;
DFS(u, id);
Mn[v] = min(Mn[v], Mn[u]);
}
}
M[v] = 2;
}
void DFS2(int v, int p, int pc)
{
C[v] = pc; M[v] = 1;
for (int &id : Adj[v])
{
if (id == p)
continue;
int u = from[id] ^ to[id] ^ v;
if (M[u])
continue;
if (Mn[u] < H[u])
DFS2(u, id, pc);
else
{
++ cp;
Ad[pc].pb(id);
Ad[cp].pb(id);
P[cp][0] = pc;
Hc[cp] = Hc[pc] + 1;
DFS2(u, id, cp);
}
}
}
void DFS3(int v, int p)
{
for (int &id : Ad[v])
{
if (id == p)
continue;
int u = from[id];
if (C[u] == v)
u = to[id];
DFS3(C[u], id);
up[v] = max(up[v], up[u] - 1);
dn[v] = max(dn[v], dn[u] - 1);
}
if (up[v] && dn[v])
exit(1);
if (up[v])
{
if (C[from[p]] == v)
R[p] = 'R';
else
R[p] = 'L';
}
if (dn[v])
{
if (C[from[p]] == v)
R[p] = 'L';
else
R[p] = 'R';
}
}
inline int LCA(int v, int u)
{
if (Hc[v] < Hc[u])
swap(v, u);
for (int i = 0; i < LG; i++)
if ((Hc[v] - Hc[u]) & (1 << i))
v = P[v][i];
if (v == u)
return (v);
for (int i = LG - 1; ~i; i--)
if (P[v][i] != P[u][i])
v = P[v][i], u = P[u][i];
return (P[v][0]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &from[i], &to[i]);
Adj[from[i]].pb(i);
Adj[to[i]].pb(i);
R[i] = 'B';
}
scanf("%d", &q);
for (int i = 1; i <= q; i++)
scanf("%d%d", &qa[i], &qb[i]);
for (int i = 1; i <= n; i++)
if (!M[i])
DFS(i, -1);
memset(M, 0, sizeof(M));
for (int i = 1; i <= n; i++)
if (!M[i])
DFS2(i, -1, ++ cp);
for (int i = 1; i < LG; i++)
for (int v = 1; v <= cp; v ++)
P[v][i] = P[P[v][i - 1]][i - 1];
for (int i = 1; i <= q; i++)
{
int a = qa[i], b = qb[i];
if (C[a] == C[b])
continue;
int lca = LCA(C[a], C[b]);
up[C[a]] = max(up[C[a]], Hc[C[a]] - Hc[lca]);
dn[C[b]] = max(dn[C[b]], Hc[C[b]] - Hc[lca]);
}
memset(M, 0, sizeof(M));
for (int i = 1; i <= cp; i++)
if (!M[i])
DFS3(i, -1);
printf("%s\n", R + 1);
return (0);
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &from[i], &to[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
oneway.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &qa[i], &qb[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
