# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1071572 | kiethm07 | One-Way Streets (CEOI17_oneway) | C++11 | 72 ms | 24148 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 5;
vector<pii> a[N];
vector<pii> t[N];
int n,m,q;
int low[N], num[N];
int component[N];
bool bridge[N];
bool inv[N];
int pa[N], sz[N], head[N], pos[N], d_hld[N], id;
int val[N];
int ans[N];
int cnt = 0;
struct edge{
int u,v;
edge(){}
};
edge e[N];
void dfs1(int u,int pre){
low[u] = num[u] = ++cnt;
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i].fi;
int id = a[u][i].se;
if (id == pre) continue;
if (num[v] != 0){
low[u] = min(low[u], num[v]);
}
else{
dfs1(v,id);
low[u] = min(low[u], low[v]);
}
bridge[id] = low[v] == num[v];
}
}
void build(int u,int c){
component[u] = c;
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i].fi;
int id = a[u][i].se;
if (bridge[id]) continue;
if (component[v] != 0) continue;
build(v,c);
}
}
void dfs2(int u,int p){
sz[u] = 1;
for (int i = 0; i < t[u].size(); i++){
int v = t[u][i].fi;
int id = t[u][i].se;
if (v == p) continue;
inv[id] = u != component[e[id].u];
pa[v] = u;
dfs2(v,u);
sz[u] += sz[v];
}
}
void hld(int u,int p){
pos[u] = ++id;
int cur = 0;
int nxt = -1;
for (int i = 0; i < t[u].size(); i++){
int v = t[u][i].fi;
if (v == p) continue;
if (sz[v] > cur){
cur = sz[v];
nxt = v;
}
}
if (nxt != -1){
head[nxt] = head[u];
d_hld[nxt] = d_hld[u];
hld(nxt,u);
for (int i = 0; i < t[u].size(); i++){
int v = t[u][i].fi;
if (v == p || v == nxt) continue;
head[v] = v;
d_hld[v] = d_hld[u] + 1;
hld(v,u);
}
}
}
int lca(int u,int v){
if (d_hld[u] < d_hld[v]) swap(u,v);
while(d_hld[u] > d_hld[v]) u = pa[head[u]];
while(head[u] != head[v]){
u = pa[head[u]];
v = pa[head[v]];
}
if (pos[u] > pos[v]) swap(u,v);
return u;
}
void dfs3(int u,int p){
for (int i = 0; i < t[u].size(); i++){
int v = t[u][i].fi;
int id = t[u][i].se;
if (v == p) continue;
dfs3(v,u);
if (val[v] < 0) ans[id] = -1;
else if (val[v] > 0) ans[id] = 1;
val[u] += val[v];
}
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
#define repdimahuhu "Phanluong"
if (fopen(repdimahuhu".inp","r")){
freopen(repdimahuhu".inp","r",stdin);
freopen(repdimahuhu".out","w",stdout);
}
cin >> n >> m;
for (int i = 1; i <= m; i++){
int u,v;
cin >> u >> v;
a[u].push_back(pii(v,i));
a[v].push_back(pii(u,i));
e[i].u = u;
e[i].v = v;
}
for (int i = 1; i <= n; i++){
if (num[i] == 0) dfs1(i,-1);
}
cnt = 0;
for (int i = 1; i <= n; i++){
if (component[i] != 0) continue;
build(i,++cnt);
}
for (int i = 1; i <= m; i++){
int u = component[e[i].u];
int v = component[e[i].v];
if (u == v) continue;
t[u].push_back(pii(v,i));
t[v].push_back(pii(u,i));
}
for (int i = 1; i <= cnt; i++){
if (pa[i] != 0) continue;
pa[i] = -1;
dfs2(i,-1);
head[i] = i;
hld(i,-1);
}
cin >> q;
while(q--){
int u,v;
cin >> u >> v;
u = component[u];
v = component[v];
val[u] += 1;
val[v] -= 1;
}
for (int i = 1; i <= cnt; i++){
if (pa[i] != -1) continue;
dfs3(i,-1);
}
// for (int i = 1; i <= m; i++){
// int u = e[i].u;
// int v = e[i].v;
// cout << u << " " << v << " " << inv[i] << "\n";
// }
for (int i = 1; i <= m; i++){
if (inv[i]) ans[i] *= -1;
if (ans[i] == 0) cout << "B";
if (ans[i] == -1) cout << "R";
if (ans[i] == 1) cout << "L";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |