#include<bits/stdc++.h>
using namespace std;
struct edge{
int u, v;
};
int n, m;
vector<vector<int> > g, in, out;
vector<vector<int> > newg;
vector<edge> e;
int next(int cur, int eid){
assert(eid < e.size());
return e[eid].u + e[eid].v - cur;
}
vector<int> vis1, evis;
void dfs(int cur){
vis1[cur] = 1;
for(int eid: g[cur]){
if(evis[eid]) continue;
evis[eid] = 1;
int adj = next(cur, eid);
out[cur].push_back(eid);
in[adj].push_back(eid);
if(!vis1[adj]) dfs(adj);
}
}
//SCC code
vector<int> euler;
void dfs2(int cur){
vis1[cur] = 1;
for(int eid: out[cur]){
int adj = next(cur, eid);
if(vis1[adj] == 0) dfs2(adj);
}
euler.push_back(cur);
}
void dfs3(int cur, int comp){
vis1[cur] = comp;
for(int eid: in[cur]){
int adj = next(cur, eid);
if(vis1[adj] == -1) dfs3(adj, comp);
}
}
vector<int> val;
vector<char> ans;
int visCount = 0;
void dfs4(int cur, int parid){
visCount++;
for(int eid: newg[cur]){
if(eid == parid) continue;
int adj = vis1[e[eid].u] + vis1[e[eid].v] - cur;
assert(adj != cur) ;
dfs4(adj, eid);
val[cur] += val[adj];
}
if(parid != -1){
if(val[cur] == 0) ans[parid] = 'B';
else if((val[cur] > 0)^(vis1[e[parid].u] == cur)){
ans[parid] = 'R';
}else{
ans[parid] = 'L';
}
}else{
assert(val[cur] == 0);
}
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
g.resize(n);
in.resize(n);
out.resize(n);
e.resize(m);
ans.resize(m);
for(int i = 0; i < m; i++){
int u, v; cin>>u>>v; u--, v--;
e[i] = {u, v};
if(u == v) continue;
g[u].push_back(i);
g[v].push_back(i);
}
vis1 = vector<int>(n, 0);
evis = vector<int>(m, 0);
dfs(0);
vis1 = vector<int>(n, 0);
for(int i = 0; i < n; i++){
if(!vis1[i]) dfs2(i);
}
reverse(euler.begin(), euler.end());
vis1 = vector<int>(n, -1);
int compCount = 0;
for(int u: euler){
if(vis1[u] == -1){
dfs3(u, u);
compCount++;
}
}
// for(int i = 0; i < n; i++){
// cout<<i<<" : "<<vis1[i]<<endl;
// }
in.clear(); out.clear();
newg.resize(n);
int edgeCount = 0;
for(int i = 0; i < m; i++){
int u = vis1[e[i].u], v = vis1[e[i].v];
if(u == v){
ans[i] = 'B';
continue;
}
edgeCount++;
newg[u].push_back(i);
newg[v].push_back(i);
}
assert(compCount - 1 == edgeCount);
//made tree
int q; cin>>q;
val.resize(n);
for(int i = 0; i < q; i++){
int x, y; cin>>x>>y; x--, y--;
x = vis1[x], y= vis1[y];
//if(x == y) continue;
val[x] -= 1;
val[y] += 1;
}
assert(vis1[0] == 0);
dfs4(0, -1);
assert(visCount == compCount);
for(int i = 0; i < m; i++){
if(ans[i] == 'B' || ans[i] == 'R' || ans[i] == 'L'){
cout<<ans[i];
}else{
//assert(false);
}
}
cout<<endl;
return 0;
}
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from oneway.cpp:1:
oneway.cpp: In function 'int next(int, int)':
oneway.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(eid < e.size());
~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
