Submission #934525

#	Time	Username	Problem	Language	Result	Execution time	Memory
934525		a_l_i_r_e_z_a	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	6488 KiB

oneway

// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
int n, m, p, h[maxn], dp[maxn], sz[maxn], par[maxn], val[maxn];
vector<pair<int, pii>> adj[maxn], g[maxn];
pii ed[maxn];
char ans[maxn];
bool mark[maxn], cut[maxn];

int find(int u){
    return u == par[u] ? u : par[u] = find(par[u]);
}

void merge(int u, int v){
    u = find(u);
    v = find(v);
    if(u == v) return;
    if(sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

void dfs_cut(int v, int p){
    dp[v] = h[v];
    mark[v] = 1;
    for(auto [u, e]: adj[v]){
        if(p == e.F) continue;
        if(!mark[u]){
            h[u] = h[v] + 1;
            dfs_cut(u, e.F);
            if(dp[u] > h[v]) cut[e.F] = 1;
        }
        smin(dp[v], dp[u]);
    }
}

void dfs(int v, int p = -1, int pe = -1, int d = -1){
    mark[v] = 1;
    for(auto [u, e]: g[v]){
        if(u == p) continue;
        dfs(u, v, e.F, e.S);
        val[v] += val[u];
    }
    if(p == -1) return;
    if(val[v] == 0){
        ans[pe] = 'B';
        return;
    }
    if(val[v] < 0){
        if(d == 1) ans[pe] = 'R';
        else ans[pe] = 'L';
    }
    else{
        if(d == 0) ans[pe] = 'R';
        else ans[pe] = 'L';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        par[i] = i;
        sz[i] = 1;
    }
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(mp(v, mp(i, 1)));
        adj[v].pb(mp(u, mp(i, 0)));
        ed[i] = mp(u, v);
    }
    dfs_cut(1, -1);
    for(int i = 0; i < m; i++){
        if(cut[i]) continue;
        ans[i] = 'B';
        merge(ed[i].F, ed[i].S);
    }
    for(int i = 0; i < m; i++){
        if(!cut[i]) continue;
        int v = find(ed[i].F), u = find(ed[i].S);
        g[v].pb(mp(u, mp(i, 1)));
        g[u].pb(mp(v, mp(i, 0)));
    }
    cin >> p;
    for(int i = 0; i < p; i++){
        int u, v; cin >> u >> v;
        u = find(u), v = find(v);
        val[u]++;
        val[v]--;
    }
    fill(mark + 1, mark + n + 1, 0);
    for(int i = 1; i <= n; i++){
        if(!mark[find(i)]) dfs(find(i));
    }
    for(int i = 0; i < m; i++) cout << ans[i];

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40