이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++)
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--)
#define ii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
//#define int long long
#define ld long double
const int maxn = 2e5 + 5;
int n, m;
vector<pair<int, ii> > g[maxn]; ii E[maxn];
int tin[maxn];
int tinpt;
int low[maxn];
bool bridge[maxn];
stack<int> st;
int cc[maxn];
int q;
int x[maxn];
int y[maxn];
vector<pair<int, ii> > g2[maxn];
int tout[maxn];
int dep[maxn];
int par[maxn][20];
int parid[maxn];
int pardir[maxn];
int dir[maxn][20];
int ans[maxn];
void dfs_prep(int u, int pid) {
tin[u] = low[u] = ++tinpt;
st.push(u);
for(auto e: g[u]) {
int v = e.fi, id = e.se.fi, dir = e.se.se;
if(id == pid) continue;
if(!tin[v]) {
dfs_prep(v, id);
low[u] = min(low[u], low[v]);
}
else if(tin[v] < tin[u]) {
low[u] = min(low[u], tin[v]);
}
}
if(low[u] >= tin[u]) {
while(1) {
int top = st.top();
cc[top] = u;
st.pop();
if(top == u) break;
}
if(pid >= 0) bridge[pid] = 1;
}
}
void dfs_prep_2(int u, int p) {
tin[u] = ++tinpt;
fori(bit, 1, 19) {
par[u][bit] = par[par[u][bit - 1]][bit - 1];
}
for(auto e: g2[u]) {
int v = e.fi, id = e.se.fi, dir = e.se.se;
if(v - p) {
dep[v] = dep[u] + 1;
par[v][0] = u;
parid[v] = id;
pardir[v] = dir ^ 1;
dfs_prep_2(v, u);
}
}
tout[u] = tinpt;
}
bool isan(int u, int v) {
return tin[u] <= tin[v] and tout[v] <= tout[u];
}
void jump(int u, int v, int dir) {
if(isan(u, v)) return;
//cout << "jump " << u << v << endl;
ford(bit, 19, 0) {
if(isan(par[u][bit], v)) continue;
::dir[u][bit] = dir;
u = par[u][bit];
}
::dir[u][0] = dir;
// cout << "lca: " << par[u][0] << endl;
}
signed main() {
// freopen("oneway.inp", "r", stdin);
// freopen("oneway.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
fori(i, 1, m) {
int u, v;
cin >> u >> v;
E[i] = ii(u, v);
g[u].eb(make_pair(v, ii(i, 0)));
g[v].eb(make_pair(u, ii(i, 1)));
}
fori(i, 1, n) if(!tin[i]) dfs_prep(i, -1);
//fori(i, 1, n) cout << cc[i] << endl;
fori(i, 1, m) if(bridge[i]) g2[cc[E[i].fi]].eb(make_pair(cc[E[i].se], ii(i, 0))), g2[cc[E[i].se]].eb(make_pair(cc[E[i].fi], ii(i, 1)));
//
tinpt = 0;
fill(tin + 1, tin + n + 1, 0ll);
fori(i, 1, n) if(!tin[i]) {
par[i][0] = i;
dfs_prep_2(i, i);
}
cin >> q;
fori(i, 1, q) {
cin >> x[i] >> y[i];
if(cc[x[i]] == cc[y[i]]) continue;
jump(cc[x[i]], cc[y[i]], 1);
jump(cc[y[i]], cc[x[i]], 2);
}
ford(bit, 19, 1) {
fori(i, 1, n) {
if(dir[i][bit]) {
dir[i][bit - 1] = dir[i][bit];
dir[par[i][bit - 1]][bit - 1] = dir[i][bit];
}
}
}
fori(i, 1, n) {
if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1;
}
fori(i, 1, m) {
if(ans[i] == 1) cout << "R";
else if(ans[i] == 2) cout << "L";
else cout << "B";
}
}
컴파일 시 표준 에러 (stderr) 메시지
oneway.cpp: In function 'void dfs_prep(int, int)':
oneway.cpp:49:31: warning: unused variable 'dir' [-Wunused-variable]
49 | int v = e.fi, id = e.se.fi, dir = e.se.se;
| ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:77: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
152 | if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1;
| ~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |