제출 #938283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938283		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	265 ms	63400 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector <vector<ar<int,2>>> adj(n);
    vector <ar<int,2>> E;
    map <int,map<int,int>> mp;
    for ( int i = 0; i < m; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        adj[u].pb({v, i});
        adj[v].pb({u, i});
        E.pb({u, v});
        mp[u][v]++;
        mp[v][u]++;
    }
    int p; cin >> p;
    vector <vector<ar<int,2>>> q(n);
    for ( int i = 0; i < p; i++ ){
        int x, y; cin >> x >> y;
        --x, --y;
        q[x].pb({y, 0});
        q[y].pb({x, 1});
    }
    vector <int> us(n), tin(n), tout(n), dir(m);
    int ct = 0;
    auto trav = [&](auto trav, int u, int p) -> void{
        us[u] = true;
        tin[u] = ++ct;
        for ( auto &[v, j]: adj[u] ){
            if ( v != p && !us[v] ){
                if ( E[j] == ar<int,2>{u, v} ){
                    dir[j] = 1;
                }
                trav(trav, v, u);
            }
        } tout[u] = ct;
    };
    vector <int> roots;
    for ( int i = 0; i < n; i++ ){
        if ( !us[i] ){
            roots.pb(i);
            trav(trav, i, -1);
        }
    }
    vector <int> low(n), ans(m, -1);
    vector <pair<int,int>> mn(n), mx(n);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        mn[u] = {n + 1, -1};
        mx[u] = {0, -1};
        for ( auto &[v, t]: q[u] ){
            chmin(mn[u], pair<int,int>{tin[v], t});
            chmax(mx[u], pair<int,int>{tout[v], t});
        }
        low[u] = tin[u];
        vector <ar<int,2>> tmp;
        for ( auto &[v, j]: adj[u] ){
            if ( v != p ){
                if ( low[v] ){
                    chmin(low[u], tin[v]);
                } else{
                    dfs(dfs, v, u);
                    chmin(mn[u], mn[v]);
                    chmax(mx[u], mx[v]);
                    chmin(low[u], low[v]);
                    if ( low[v] > tin[u] ){
                        tmp.pb({v, j});
                    }
                }
            }
        }
        for ( auto &[v, j]: tmp ){
            if ( mn[v].first < tin[v] ){
                ans[j] = mn[v].second;
            }
            if ( mx[v].first > tout[v] ){
                ans[j] = mx[v].second;
            }
        }
    };
    for ( auto &u: roots ){
        dfs(dfs, u, -1);
    }
    for ( int i = 0; i < m; i++ ){
        auto [u, v] = E[i];
        if ( mp[u][v] > 1 ){
            ans[i] = -1;
        }
    }
    int it = 0;
    for ( auto &x: ans ){
        x ^= dir[it++];
        cout << (x > 0 ? 'L' : x < 0 ? 'B' : 'R');
    }

    cout << '\n';
}

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