#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
struct dsu1 {
int n;
vector<int> p, r;
dsu1(int size) {
n = size;
p.resize(n), r.resize(n, 0);
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
if (r[x] < r[y]) p[x] = y;
else {
p[y] = x;
if (r[x] == r[y]) r[x]++;
}
}
}
vector<vector<int>> calc() {
vector<vector<int>> a(n);
for (int i = 0; i < n; i++) a[p[i]].push_back(i);
vector<vector<int>> rtn;
for (auto &i : a)
if (i.size() > 1) rtn.push_back(i);
return rtn;
}
};
struct dsutree {
int n;
vector<int> p;
dsutree(int size = 0) {
n = size;
p.resize(n);
for (int i = 0; i < n; i++) p[i] = i;
}
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void remove(int v, int par) {
p[v] = par;
}
};
struct edge {
int st, to, ind;
bool thisway;
edge(int ss = 0, int tt = 0, int ii = -1, bool _thisway = false) {
st = ss;
to = tt;
ind = ii;
thisway = _thisway;
}
};
int n, m, q, nn;
vector<int> dep, mn, vis;
vector<vector<edge>> g, t;
vector<vector<int>> cycles;
vector<int> incycle, par;
vector<edge> epar;
string ans;
int dfs(int v = 0, edge preve = edge(), int d = 0) {
if (vis[v]) return dep[v];
vis[v] = 1;
dep[v] = d;
mn[v] = d;
for (const auto &i : g[v])
if (i.ind != preve.ind)
mn[v] = min(mn[v], dfs(i.to, i, d + 1));
return mn[v];
}
void preprocess(int v = 0, int d = 0, edge preve = edge()) {
if (vis[v]) return;
// cout << "vertex " << v << " with prev being " << preve.st << endl;
dep[v] = d;
vis[v] = 1;
epar[v] = preve;
for (const auto &i : t[v])
preprocess(i.to, d + 1, i);
}
int main() {
fast;
cin >> n >> m;
ans = string(m, 'B');
g.resize(n);
dep.resize(n, 0);
mn.resize(n, 1e9);
vis.resize(n, 0);
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
--u, --v;
g[u].push_back(edge(u, v, i, true));
g[v].push_back(edge(v, u, i, false));
}
dsu1 d1(n);
for (int i = 0; i < n; i++)
if (!vis[i])
dfs(i);
// for (int i = 0; i < n; i++)
// cout << "vertex " << i << " with depth " << dep[i] << " and mn " << mn[i] << endl;
for (const auto &i : g)
for (const auto &j : i)
if (dep[j.to] > mn[j.to] && dep[j.st] < dep[j.to] && dep[j.st] >= mn[j.to]) d1.unite(j.st, j.to);
cycles = d1.calc();
incycle.resize(n, -1);
for (int i = 0; i < cycles.size(); i++)
for (const auto &j : cycles[i])
incycle[j] = i;
nn = n + cycles.size();
t.resize(nn);
d1 = dsu1(nn);
int n1, n2;
for (const auto &i : g)
for (const auto &j : i) {
if (j.st < j.to) { // makes sure to count edges only once
if (incycle[j.st] > -1) n1 = n + incycle[j.st];
else n1 = j.st;
if (incycle[j.to] > -1) n2 = n + incycle[j.to];
else n2 = j.to;
if (d1.find(n1) != d1.find(n2)) {
d1.unite(n1, n2);
t[n1].push_back(edge(n1, n2, j.ind, j.thisway));
t[n2].push_back(edge(n2, n1, j.ind, !j.thisway));
}
}
}
epar.resize(nn);
vis.resize(nn);
dep.resize(nn);
for (auto &i : vis) i = 0;
for (int i = 0; i < nn; i++)
if (!vis[i])
preprocess(i);
dsutree d2(nn);
/*
cout << "cycles" << endl;
for (const auto &i : cycles) {
for (const auto &j : i) cout << j << " "; cout << endl;
}
cout << "new tree" << endl;
for (const auto &i : t)
for (const auto &j : i)
cout << j.st << " " << j.to << " with ind " << j.ind << " and direction being " << j.thisway << endl;
cout << "parents" << endl;
for (int i = 0; i < nn; i++)
cout << "parent of " << i << " is " << epar[i].st << endl << "depth of " << i << " is " << dep[i] << endl;
*/
cin >> q;
for (int i = 0, st, en; i < q; i++) {
cin >> st >> en;
--st, --en;
if (incycle[st] != -1) st = incycle[st] + n;
if (incycle[en] != -1) en = incycle[en] + n;
st = d2.find(st), en = d2.find(en);
// debug;
while (st != en) {
// cout << st << " " << en << endl;
if (dep[st] > dep[en]) {
// cout << "the way is " << epar[st].thisway << endl;
if (epar[st].thisway) ans[epar[st].ind] = 'L';
else ans[epar[st].ind] = 'R';
d2.remove(st, epar[st].st);
st = d2.find(st);
}
else {
// cout << "the way is " << epar[en].thisway << endl;
if (epar[en].thisway) ans[epar[en].ind] = 'R';
else ans[epar[en].ind] = 'L';
d2.remove(en, epar[en].st);
en = d2.find(en);
}
}
}
cout << ans << endl;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:145:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cycles.size(); i++)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
360 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
360 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
360 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
