#include <bits/stdc++.h>
using namespace std;
const int mxN=1e5;
int n, m, k, a[mxN], b[mxN], ab[mxN], d[mxN], s[mxN], p[mxN], r[mxN], dt=1, tin[mxN], low[mxN];
bool bg[mxN];
vector<int> adj[mxN];
int find(int x) {
return x==p[x]?x:(p[x]=find(p[x]));
}
inline void join(int x, int y) {
if((x=find(x))==(y=find(y)))
return;
if(r[x]<r[y])
p[x]=y;
else
p[y]=x;
if(r[x]==r[y])
++r[x];
}
void dfs1(int u, int p) {
tin[u]=low[u]=dt++;
for(int e : adj[u]) {
int v=u^ab[e];
if(!tin[v]) {
dfs1(v, e);
low[u]=min(low[v], low[u]);
if(low[v]>tin[u])
bg[e]=1;
} else if(e!=p)
low[u]=min(tin[v], low[u]);
}
}
void dfs2(int u, int p) {
for(int e : adj[u]) {
int v=u^ab[e];
if(v==p)
continue;
d[v]=d[u]+1;
dfs2(v, u);
s[u]+=s[v];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; ++i)
p[i]=i;
for(int i=0; i<m; ++i) {
cin >> a[i] >> b[i], --a[i], --b[i];
ab[i]=a[i]^b[i];
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
for(int i=0; i<n; ++i)
if(!tin[i])
dfs1(i, -1);
for(int i=0; i<m; ++i)
if(!bg[i])
join(a[i], b[i]);
for(int i=0; i<n; ++i)
adj[i].clear();
for(int i=0; i<m; ++i) {
if(!bg[i])
continue;
a[i]=find(a[i]);
b[i]=find(b[i]);
ab[i]=a[i]^b[i];
adj[a[i]].push_back(i);
adj[b[i]].push_back(i);
}
cin >> k;
while(k--) {
int x, y;
cin >> x >> y, --x, --y;
++s[find(x)], --s[find(y)];
}
for(int i=0; i<n; ++i) {
if(p[i]==i&&!d[i]) {
d[i]=1;
dfs2(i, -1);
}
}
for(int i=0; i<m; ++i) {
if(!bg[i]) {
cout << 'B';
continue;
}
int u=d[a[i]]>d[b[i]]?a[i]:b[i];
cout << (s[u]?((s[u]>0)==(u==a[i])?'R':'L'):'B');
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2916 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2916 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2916 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2916 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2924 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2976 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3036 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2916 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2916 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2916 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2916 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2924 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2976 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3036 KB |
Output is correct |
| 11 |
Correct |
50 ms |
7220 KB |
Output is correct |
| 12 |
Correct |
61 ms |
8536 KB |
Output is correct |
| 13 |
Correct |
70 ms |
9924 KB |
Output is correct |
| 14 |
Correct |
107 ms |
11220 KB |
Output is correct |
| 15 |
Correct |
191 ms |
11476 KB |
Output is correct |
| 16 |
Correct |
120 ms |
11476 KB |
Output is correct |
| 17 |
Correct |
112 ms |
11476 KB |
Output is correct |
| 18 |
Correct |
92 ms |
11476 KB |
Output is correct |
| 19 |
Correct |
111 ms |
12392 KB |
Output is correct |
| 20 |
Correct |
75 ms |
12392 KB |
Output is correct |
| 21 |
Correct |
56 ms |
12392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2916 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2916 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2916 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2916 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2924 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2976 KB |
Output is correct |
| 8 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3036 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3036 KB |
Output is correct |
| 11 |
Correct |
50 ms |
7220 KB |
Output is correct |
| 12 |
Correct |
61 ms |
8536 KB |
Output is correct |
| 13 |
Correct |
70 ms |
9924 KB |
Output is correct |
| 14 |
Correct |
107 ms |
11220 KB |
Output is correct |
| 15 |
Correct |
191 ms |
11476 KB |
Output is correct |
| 16 |
Correct |
120 ms |
11476 KB |
Output is correct |
| 17 |
Correct |
112 ms |
11476 KB |
Output is correct |
| 18 |
Correct |
92 ms |
11476 KB |
Output is correct |
| 19 |
Correct |
111 ms |
12392 KB |
Output is correct |
| 20 |
Correct |
75 ms |
12392 KB |
Output is correct |
| 21 |
Correct |
56 ms |
12392 KB |
Output is correct |
| 22 |
Correct |
137 ms |
12392 KB |
Output is correct |
| 23 |
Correct |
132 ms |
12392 KB |
Output is correct |
| 24 |
Correct |
157 ms |
12392 KB |
Output is correct |
| 25 |
Correct |
334 ms |
14076 KB |
Output is correct |
| 26 |
Correct |
135 ms |
14076 KB |
Output is correct |
| 27 |
Correct |
124 ms |
14076 KB |
Output is correct |
| 28 |
Correct |
44 ms |
14076 KB |
Output is correct |
| 29 |
Correct |
104 ms |
14076 KB |
Output is correct |
| 30 |
Correct |
77 ms |
14076 KB |
Output is correct |
| 31 |
Correct |
99 ms |
14076 KB |
Output is correct |
| 32 |
Correct |
108 ms |
14076 KB |
Output is correct |
