#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
vector <pair <int, int>> g[N];
vector <pair <int, int>> backedges[N];
int l[N], r[N];
int mark[N];
set <array <int, 3>> edges;
vector <array <int, 3>> arestas;
int tin[N], low[N], pai[N];
int tmm = 1;
char res[N];
map <pair <int,int>, int> look;
int aux[N];
int sz[N];
void dfs3(int v, int p){
int val = -1;
aux[v] = 1;
sz[v] = l[v]-r[v];
for(auto [x, i] : g[v]){
if(x == p){
val = i;
continue;
}
dfs3(x, v);
sz[v] += sz[x];
}
if(val == -1) return;
if(res[val] == 'B') return;
if(sz[v] == 0){
res[val] = 'B';
}
else if(sz[v] > 0){
res[val] = 'U';
}
else{
res[val] = 'D';
}
}
void dfs2(int v, int p){
pai[v] = p;
tin[v] = tmm;
tmm++;
low[v] = tin[v];
for(auto [x,i] : backedges[v]){
if(tin[x] == 0) continue;
low[v] = min(low[v], tin[x]);
}
for(auto [x,i] : g[v]){
if(x == p) continue;
dfs2(x,v);
low[v] = min(low[v], low[x]);
}
tmm++;
return;
}
void dfs(int v, int p){
mark[v] = 1;
for(auto [x, i] : g[v]){
if(x == p) continue;
if(mark[x] == 1) continue;
edges.insert({v, x, i});
edges.insert({x, v, i});
dfs(x, v);
}
return;
}
map <pair <int, int>, int> buceta;
int main(){
int n, m;
cin >> n >> m;
for(int i = 0;i < m;i++){
int a, b;
cin >> a >> b;
g[a].push_back({b, i});
g[b].push_back({a, i});
arestas.push_back({a, b, i});
look[{a, b}] = i;
look[{b, a}] = i;
buceta[{a, b}] = 0;
buceta[{b, a}] = 1;
}
int q;
cin >> q;
while(q--){
int a, b;cin >> a >> b;
l[a]++;
r[b]++;
}
for(int i = 1;i <= n;i++){
if(mark[i] == 0) dfs(i, i);
}
for(int i = 1;i <= n;i++) g[i].clear();
for(auto [a, b, i] : edges){
g[a].push_back({b, i});
}
for(auto [a, b, i] : arestas){
if(edges.find({a, b, i}) != edges.end()) continue;
backedges[a].push_back({b, i});
backedges[b].push_back({a, i});
res[i] = 'B';
}
for(int i = 1;i <= n;i++){
if(pai[i] == 0){
dfs2(i, i);
}
}
for(int i = 1;i <= n;i++){
if(i == pai[i]) continue;
if(low[i] <= tin[pai[i]]){
int t = look[{i, pai[i]}];
res[t] = 'B';
}
}
for(int i = 1;i <= n;i++){
if(aux[i] == 0) dfs3(i, i);
}
for(int i = 1;i <= n;i++){
if(i == pai[i]) continue;
int val = look[{i, pai[i]}];
if(res[val] == 'B') continue;
if(buceta[{i, pai[i]}] == 0){
if(res[val] == 'U') res[val] = 'R';
else res[val] = 'L';
}
else{
if(res[val] == 'U') res[val] = 'L';
else res[val] = 'R';
}
}
for(int i = 0;i < m;i++){
cout << res[i];
}
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8016 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8016 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
8588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8016 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8016 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
8588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8016 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8016 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
8588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
