#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i,T j) { return i > j ? i = j,true: false; }
template<class T> bool cmax(T &i,T j) { return i < j ? i = j,true: false; }
struct RMQ {
int n;
int lg;
vector<vector<int>> sparse;
RMQ() {}
RMQ(vector<int> a) {
if (a.empty()) { return; }
n = (int)a.size();
lg = 0;
while((1<<lg) <= n) { lg++; }
sparse.assign(lg,vector<int>(n));
sparse[0] = a;
for (int pw=1;pw<lg;pw++) {
for (int i=0;i<n;i++) {
sparse[pw][i] = min(sparse[pw-1][i],sparse[pw-1][min(i+(1<<(pw-1)),n-1)]);
}
}
}
int qry(int l,int r) {
assert(0 <= l && l <= r && r < n);
int bit = 31-__builtin_clz(r-l+1);
return min(sparse[bit][l],sparse[bit][r-(1<<bit)+1]);
}
};
struct LCA {
int n;
vector<vector<pair<int,int>>> adj;
vector<int> tin,path,ret;
RMQ rmq;
int timer = 0;
LCA(int N,vector<vector<pair<int,int>>> a) {
adj = a;
n = N;
tin.resize(n);
dfs();
rmq = RMQ(ret);
}
void dfs(int x=0,int z=-1) {
tin[x] = timer++;
for (auto &[y,idx]: adj[x]) if (y != z) {
path.push_back(x),ret.push_back(tin[x]);
dfs(y,x);
}
}
int lca(int x,int y) {
if (x == y) { return x; }
if (tin[x] > tin[y]) { swap(x,y); }
return path[rmq.qry(tin[x],tin[y]-1)];
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
string ans(m,'B');
vector<vector<pair<int,int>>> adj(n);
vector<pair<int,int>> edges(m);
for (int i=0,x,y;i<m;i++) {
cin >> x >> y;
--x,--y;
edges[i] = make_pair(x,y);
adj[x].emplace_back(y,i);
adj[y].emplace_back(x,i);
}
vector<vector<pair<int,int>>> tree(n);
// vector<vector<pair<int,int>>> back_edges(n);
vector<int> dp(n);
vector<int> t(n,-1);
int timer = 0;
auto dfs = [&](auto &self,int x,int z) -> void {
t[x] = timer++;
for (auto &[y,idx]: adj[x]) if (y != z) {
if (t[y] > t[x]) {
// back_edges[y].emplace_back(x,idx);
// cout << "back edge: " << y+1 << " " << x+1 << endl;
dp[y]++;
dp[x]--;
} else if (t[y] == -1) {
tree[x].emplace_back(y,idx);
// cout << "span edge: " << x+1 << " " << y+1 << endl;
self(self,y,x);
}
}
};
dfs(dfs,0,-1);
if (timer < n) { while(1) {} }
auto dfstree = [&](auto &self,int x,int z) -> void {
for (auto &[y,idx]: tree[x]) if (y != z) {
self(self,y,x);
dp[x] += dp[y];
}
};
dfstree(dfstree,0,-1);
vector<int> up(n),down(n);
LCA tr(n,tree);
int q;
cin >> q;
for (int x,y;q--;) {
cin >> x >> y;
int l = tr.lca(--x,--y);
up[x]++;
up[l]--;
down[y]++;
down[l]--;
}
auto dfspush = [&](auto &self,int x,int z) -> void {
for (auto &[y,idx]: tree[x]) if (y != z) {
self(self,y,x);
up[x] += up[y];
down[x] += down[y];
// actually write down edge
if (dp[y] != 0) { continue; }
assert(up[y] == 0 || down[y] == 0);
if (up[y]) {
if (edges[idx].second == x) {
ans[idx] = 'R';
} else {
ans[idx] = 'L';
}
} else if (down[y]) {
if (edges[idx].second == y) {
ans[idx] = 'R';
} else {
ans[idx] = 'L';
}
}
}
};
dfspush(dfspush,0,-1);
cout << ans << endl;
}
Compilation message
oneway.cpp: In constructor 'LCA::LCA(int, std::vector<std::vector<std::pair<int, int> > >)':
oneway.cpp:8:8: warning: '<anonymous>.RMQ::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
8 | struct RMQ {
| ^~~
oneway.cpp:8:8: warning: '<anonymous>.RMQ::lg' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3040 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3040 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3040 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
