이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 1e5 + 5;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
struct Edge {
int u, v;
bool isBridge, used;
Edge(int _u = 0, int _v = 0) {
u = _u; v = _v;
isBridge = used = 0;
}
} e[N];
int n, m, q;
int low[N], num[N];
vector<int> adj[N];
vector<ii> newAdj[N];
void read() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
e[i] = Edge(u, v);
adj[u].push_back(i);
adj[v].push_back(i);
}
}
int timer = 0, cycle = 0;
stack<int> st;
int id[N];
void tarjan(int u) {
low[u] = num[u] = ++timer;
st.push(u);
for(int i: adj[u]) if (!e[i].used) {
e[i].used = 1;
int v = e[i].u ^ e[i].v ^ u;
if (num[v]) low[u] = min(low[u], num[v]);
else {
tarjan(v);
low[u] = min(low[u], low[v]);
}
if (low[v] > num[u]) {
// cerr << "BRIDGE: " << e[i].u << ' ' << e[i].v << endl;
e[i].isBridge = 1;
}
}
if (low[u] == num[u]) {
++cycle;
// cerr << cycle << endl;
while(true) {
int v = st.top(); st.pop();
// cerr << v << ' ';
low[v] = num[v] = inf;
id[v] = cycle;
if (v == u) break;
}
// cerr << endl;
}
}
int tin[N], tout[N], high[N];
ii par[N];
bool isChild(int u, int p) {
return tin[u] >= tin[p] && tin[u] <= tout[p];
}
int jump[N];
void dfs(int u, int p) {
// cerr << u << endl;
tin[u] = ++timer;
jump[u] = u;
for(auto [v, i]: newAdj[u]) if (v != p) {
par[v] = {u, i};
high[v] = high[u] + 1;
dfs(v, u);
}
tout[u] = timer;
}
int ans[N];
int change[N];
vector<int> node;
void solve() {
tarjan(1);
for(int i = 1; i <= m; i++) if (e[i].isBridge) {
int u = id[e[i].u], v = id[e[i].v];
newAdj[u].push_back({v, i});
newAdj[v].push_back({u, i});
}
timer = 0;
dfs(1, -1);
cin >> q;
while(q--) {
int u, v; cin >> u >> v;
// cerr << id[u] << ' ' << id[v] << endl;
if (id[u] == id[v]) continue;
u = id[u]; v = id[v];
int tmp = u;
// cerr << jump[u] << ' ' << v << ' ' << isChild(jump[u], v) << endl;
while(!isChild(v, u)) {
int i = par[u].se;
// u = par[u].fi;
ans[i] = 1;
// node.push_back(u);
u = par[u].fi;
}
// for(int x: node) jump[x] = u;
node.clear();
u = tmp;
while(!isChild(u, v)) {
int i = par[v].se;
ans[i] = 2;
// cerr << v << ' ' << e[i].u << ' ' << e[i].v << endl;
// node.push_back(v);
v = par[v].fi;
}
// for(int x: node) jump[x] = v;
node.clear();
}
for(int i = 1; i <= m; i++) {
// cout << e[i].u << ' ' << e[i].v << ' ';
if (e[i].isBridge) {
if (ans[i] != 0) {
int u = e[i].u, v = e[i].v;
if (high[id[u]] < high[id[v]]) {
assert(isChild(id[v], id[u]));
if (ans[i] == 2) cout << 'R';
else cout << 'L';
}
else {
assert(isChild(id[u], id[v]));
if (ans[i] == 2) cout << 'L';
else cout << 'R';
}
}
else cout << 'B';
// cout << endl;
continue;
}
else cout << 'B';
// cout << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int test = 1;
// cin >> test;
while(test--) {
read();
solve();
}
return 0;
}
// rmq - rmq2d
// hash
// fw - fw2d
// segtree
컴파일 시 표준 에러 (stderr) 메시지
oneway.cpp: In function 'int main()':
oneway.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |