oj.uz

답안 #938245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938245 2024-03-05T03:36:18 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 0 ms 348 KB 
#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);
    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});
    }
    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);
    int ct = -1;
    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] ){
                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};
        mx[u] = {-1, -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 ( auto &x: ans ){
        cout << (x > 0 ? 'L' : x < 0 ? 'B' : 'R');
    }

    cout << '\n';
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -