#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "OneWay"
int n, m, q;
class edge{
public:
int u, v, x;
void input(){
read(u);
read(v);
x=u^v;
}
int get_v(int u){
return x^u;
}
} e[100001];
char ans[100001];
vector <int> g[100001];
bool done[100001];
int p[100001];
int cnt=0;
int num[100001];
int low[100001];
bool b[100001];
int cp[100001];
int pc[100001];
int h[100001];
int f[100001][20];
void dfs(int u){
cnt++;
num[u]=low[u]=cnt;
for(int i: g[u]) if(done[i]) p[u]=i;
for(int i: g[u]) if(!done[i]){
done[i]=1;
int v=e[i].get_v(u);
if(num[v]) low[u]=min(low[u], num[v]);
else{
dfs(v);
low[u]=min(low[u], low[v]);
}
}
for(int i: g[u]){
int v=e[i].get_v(u);
if(p[v]==i) if(low[v]>num[u]) b[i]=1;
}
}
int r[100001];
int root(int u){
if(r[u]<0) return u;
return r[u]=root(r[u]);
}
void unite(int u, int v){
u=root(u);
v=root(v);
if(u==v) return;
if(r[u]>r[v]) swap(u, v);
r[u]+=r[v];
r[v]=u;
}
void dfslca(int u){
done[u]=1;
for(int i=0; f[f[u][i]][i]; i++) f[u][i+1]=f[f[u][i]][i];
for(int i: g[u]){
int v=e[i].get_v(u);
if(done[v]) continue;
p[v]=i;
f[v][0]=u;
h[v]=h[u]+1;
dfslca(v);
}
}
int lca(int u, int v){
if(h[u]<h[v]) swap(u, v);
DFOR(i, __lg(h[u]), 0) if(h[f[u][i]]>=h[v]) u=f[u][i];
if(u==v) return u;
DFOR(i, __lg(h[u]), 0) if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
return f[u][0];
}
void dfstree(int u){
for(int i: g[u]){
int v=e[i].get_v(u);
if(p[v]!=i) continue;
dfstree(v);
pc[u]=max(pc[u], pc[v]-1);
cp[u]=max(cp[u], cp[v]-1);
}
if(pc[u]){
assert(cp[u]==0);
ans[p[u]]="RL"[u==e[p[u]].u];
}
else if(cp[u]){
ans[p[u]]="LR"[u==e[p[u]].u];
}
}
int main(){
#ifdef Aria
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Aria
read(n);
read(m);
FOR(i, 1, m) ans[i]='B';
FOR(i, 1, m){
e[i].input();
if(e[i].x){
g[e[i].u].pb(i);
g[e[i].v].pb(i);
}
}
FOR(i, 1, n) if(!num[i]) dfs(i);
FOR(i, 1, n) r[i]=-1;
FOR(i, 1, m) if(!b[i]) unite(e[i].u, e[i].v);
FOR(i, 1, n) g[i].clear();
FOR(i, 1, m){
e[i].u=root(e[i].u);
e[i].v=root(e[i].v);
e[i].x=e[i].u^e[i].v;
if(e[i].x){
g[e[i].u].pb(i);
g[e[i].v].pb(i);
}
}
FOR(i, 1, n) done[i]=0;
FOR(i, 1, n) if(!done[i]){
p[i]=0;
h[i]=1;
dfslca(i);
}
read(q);
{
int u, v;
FOR(i, 1, q){
read(u);
read(v);
u=root(u);
v=root(v);
int r=lca(u, v);
cp[u]=max(cp[u], h[u]-h[r]);
pc[v]=max(pc[v], h[v]-h[r]);
}
}
FOR(i, 1, n) if(i==root(i)) dfstree(i);
FOR(i, 1, m) putchar(ans[i]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2944 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2944 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2816 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2944 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2944 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2816 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 11 |
Correct |
44 ms |
8404 KB |
Output is correct |
| 12 |
Correct |
52 ms |
10488 KB |
Output is correct |
| 13 |
Correct |
58 ms |
15096 KB |
Output is correct |
| 14 |
Correct |
95 ms |
18860 KB |
Output is correct |
| 15 |
Correct |
114 ms |
19960 KB |
Output is correct |
| 16 |
Correct |
399 ms |
19264 KB |
Output is correct |
| 17 |
Execution timed out |
3094 ms |
20700 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2944 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2944 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2816 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 11 |
Correct |
44 ms |
8404 KB |
Output is correct |
| 12 |
Correct |
52 ms |
10488 KB |
Output is correct |
| 13 |
Correct |
58 ms |
15096 KB |
Output is correct |
| 14 |
Correct |
95 ms |
18860 KB |
Output is correct |
| 15 |
Correct |
114 ms |
19960 KB |
Output is correct |
| 16 |
Correct |
399 ms |
19264 KB |
Output is correct |
| 17 |
Execution timed out |
3094 ms |
20700 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
