#include <bits/stdc++.h>
#define int int64_t //be careful about this
using namespace std;
#define vt vector
#define ar array
#define pr pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define fr(i,a,b) for(int i = (a); i < (b); ++i)
#define rf(i,a,b) for(int i = (b)-1; i >= (a); --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
namespace IN{
template<class T> void re(vector<T> &A);
template<class S,class T> void re(pair<S,T> &A);
template<class T,size_t N> void re(array<T,N> &A);
template<class T> void re(T& x){
cin >> x;}
template<class H, class... T> void re(H& h, T&... t){
re(h); re(t...);}
template<class T> void re(vector<T> &A){
for(auto& x : A) re(x);}
template<class S,class T> void re(pair<S,T> &A){
re(A.first); re(A.second);}
template<class T,size_t N> void re(array<T,N> &A){
for(int i = 0; i < N; ++i) re(A[i]);}
}
namespace OUT{
template<class T>
void __p(const T& a){ cout<<a; }
template<class T, class F>
void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
template<class T, size_t N>
void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
template<class T>
void __p(const vector<T>& a){
cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
template<class T, class ...Arg>
void __p(T a1, Arg ...a){__p(a1); __p(a...); }
template<class Arg1>
void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
template<class Arg1, class ... Args>
void __f(const char *ss, Arg1 &&arg1, Args &&... args){
int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
#define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
}
namespace FUNC{
void IO(string s = ""){
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
if(!s.empty()){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
const auto start_time = chrono::high_resolution_clock::now();
void output_run_time(){
// will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
auto end_time = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end_time-start_time;
cout << "\n\n\nTime Taken : " << diff.count();
#endif
}
template<class T> bool ckmin(T& a, const T& b){
return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, const T& b){
return a < b ? a = b, true : false; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int L, int R){
return uniform_int_distribution<int>(L,R)(rng); }
template<class T> int sz(const T& x){
return int(x.size()); }
template<class T> int lb(const vector<T>& vec,const T& val){
return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }
template<class T> int ub(const vector<T>& vec,const T& val){
return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }
constexpr int dx[4] = {1,0,-1,0};
constexpr int dy[4] = {0,1,0,-1};
constexpr char dr[4] = {'D','R','U','L'};
constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
constexpr int INF = 2e9;
template<class T>
vector<T> V(int n,T val){
return vector<T> (n,val);
}
template<class T>
vector<vector<T>> V(int n,int m,T val){
return vector<vector<T>> (n,vector<T> (m,val));
}
template<class T>
vector<vector<vector<T>>> V(int n,int m,int k,T val){
return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
}
}
using namespace IN;
using namespace OUT;
using namespace FUNC;
struct DSU {
int n, z;
// root node: -1 * component size
// otherwise: parent
vector<int> parent_or_size;
DSU(int n_ = -1){
if(n_ >= 0)
init(n_);
}
void init(int n_){
z = n = n_;
parent_or_size.assign(n_, -1);
}
bool merge(int a, int b){
int x = leader(a), y = leader(b);
if(x == y)
return false;
if(-parent_or_size[x] < -parent_or_size[y])
swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
z--;
return true;
}
bool same(int a, int b){
return leader(a) == leader(b);
}
int leader(int a){
if(parent_or_size[a] < 0)
return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a){
return -parent_or_size[leader(a)];
}
vector<vector<int>> groups(){
vector<int> leader_buf(n), group_size(n);
for(int i = 0; i < n; i++){
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
vector<vector<int>> result(n);
for(int i = 0; i < n; i++){
result[i].reserve(group_size[i]);
}
for(int i = 0; i < n; i++){
result[leader_buf[i]].push_back(i);
}
result.erase(remove_if(result.begin(), result.end(),[&](const auto& v){return v.empty(); }),result.end());
return result;
}
int comp(){
return z;
}
};
vt<pr<int,int>> bridges;
DSU dsu;
vector<vector<int>> two_edge_cc(const vector<vector<int>>& g_){
struct E{
int to,id;
};
int n = g_.size();
vector<vector<E>> g(n);
for(int i = 0, f = 0; i < n; ++i)
for(auto j : g_[i])
if(j < i){
g[j].push_back({i,f});
g[i].push_back({j,f++});
}
vector<int> depth(n,-1), up(n);
dsu.init(n);
auto dfs = [&](auto self,int node,int parent_id) -> bool {
up[node] = depth[node];
for(auto [child,id] : g[node])
if(id != parent_id)
if(depth[child] < 0){
depth[child] = depth[node] + 1;
if(!self(self,child,id)){
dsu.merge(node,child);
}else{
bridges.pb({node,child});
}
up[node] = min(up[node],up[child]);
}else{
up[node] = min(up[node],depth[child]);
}
return up[node] == depth[node];
};
for(int i = 0; i < n; ++i)
if(depth[i] < 0){
depth[i] = 0;
dfs(dfs,i,-1);
}
return dsu.groups();
}
struct LCA {
int n, lg;
vector<vector<pair<int,int>>> adj;
vector<int> depth, parent, euler, tour, tour_end, tour_start;
vector<vector<pair<int,int>>> jump;
LCA(int n = 0){
init(n);
}
void init(int _n){
n = _n;
lg = __lg(n);
adj.assign(n, {});
depth.resize(n);
parent.resize(n);
tour.resize(n);
tour_end.resize(n);
tour_start.resize(n);
euler.clear();
jump.assign(n, vector<pair<int,int>> (lg + 1));
}
void add_edge(int u,int v,int w = 1){
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
int timer;
void dfs(int x){
tour_start[x] = timer++;
tour[tour_start[x]] = x;
euler.push_back(x);
for(auto [y,w] : adj[x])
if(y != parent[x]){
depth[y] = depth[x] + 1;
parent[y] = x;
jump[y][0] = {x,w};
for(int j = 1; j <= lg; ++j)
jump[y][j] = {jump[jump[y][j-1].first][j-1].first,jump[y][j-1].second + jump[jump[y][j-1].first][j-1].second};
dfs(y);
euler.push_back(x);
}
tour_end[x] = timer;
}
void build(int R = 0){
timer = 0;
for(int j = 0; j <= lg; ++j)
jump[R][j] = {R,0};
parent[R] = R;
depth[R] = 0;
dfs(R);
}
int lca(int u, int v){
if(depth[u] < depth[v])
swap(u,v);
u = find_kth_ancestor(u, depth[u] - depth[v]).first;
if(u == v)
return u;
for(int j = lg; j >= 0; --j)
if(jump[u][j].first != jump[v][j].first)
u = jump[u][j].first, v = jump[v][j].first;
assert(jump[u][0].first == jump[v][0].first);
return jump[u][0].first;
}
int dist(int u, int v,bool weighted = true){
if(weighted){
const int x = lca(u,v);
int ret = 0;
for(auto y : {u,v})
ret += find_kth_ancestor(y,depth[y] - depth[x]).second;
return ret;
}else
return depth[u] + depth[v] - 2 * depth[lca(u,v)];
}
pair<int,int> find_kth_ancestor(int x,int k){
int dis = 0;
for(int j = 0; j <= lg; ++j)
if(k >> j & 1)
dis += jump[x][j].second, x = jump[x][j].first;
return {x, dis};
}
};
signed main(){
IO();
int n,m;
re(n,m);
vt<vt<int>> g(n);
vt<pr<int,int>> edges;
fr(e,0,m){
int u,v; re(u,v); --u,--v;
edges.push_back({u,v});
g[u].pb(v);
g[v].pb(u);
}
two_edge_cc(g);
vt<vt<int>> tree(n);
int R = dsu.leader(0);
set<pr<int,int>> chk;
for(auto [u,v] : bridges){
u = dsu.leader(u);
v = dsu.leader(v);
tree[u].pb(v);
tree[v].pb(u);
chk.insert({u,v});
}
int k;
re(k);
vt<int> val(n,0);
while(k--){
int u,v; re(u,v); --u,--v;
u = dsu.leader(u);
v = dsu.leader(v);
val[u]++;
val[v]--;
}
set<pr<int,int>> dir;
auto dfs = [&](auto self,int i,int parent) -> void {
for(auto j : tree[i])
if(j != parent){
self(self,j,i);
val[i] += val[j];
if(val[j] > 0){
dir.insert({j,i});
}else if(val[j] < 0){
dir.insert({i,j});
}
}
};
dfs(dfs,R,-1);
for(auto [u,v] : edges){
int pu = dsu.leader(u), pv = dsu.leader(v);
if(pu == pv){
cout << "B";
}else{
assert(chk.count({pu,pv}) || chk.count({pv,pu}));
if(dir.count({pu,pv})){
cout << "R";
}else if(dir.count({pv,pu})){
cout << "L";
}else{
cout << "B";
}
}
}
// output_run_time();
return 0;
}
Compilation message
oneway.cpp: In lambda function:
oneway.cpp:233:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
233 | if(id != parent_id)
| ^
oneway.cpp: In function 'void FUNC::IO(std::string)':
oneway.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
