제출 #1286054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286054		daviedu	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	85 ms	23396 KiB

oneway

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double

void dbg_out(string s) { cerr << endl; }
template<typename H, typename... T>
void dbg_out(string s, H h, T... t){
    do{ cerr << s[0]; s = s.substr(1);
    } while (sz(s) && s[0] != ',');
    cerr << " = " << h;
    dbg_out(s, t...);
}

#ifdef DEBUG
#define dbg(...) dbg_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

const int mx = 2e5+123;
// graph with vector<pair<vertex, edge_index>>
// adapt if you won't need bridges
vector<pair<int, int>> g [mx];

// you can use stacks to keep "active" vertices
// when you find art/bridge (bcc/2cc), process them until you get to vertice "v"
// remember to process the stack after each call in art_and_bridges
// because it will hold the last component
vector<int> num, art, bridge;

int dfs_art_bridges(int u, int p, int& t){
    int low = num[u] = t++;
    for (auto [v, idx]: g[u]){
        if (v == p){ // for multiedges, else just if (v != p)
            p = -1;
            continue;
        }
        if (num[v] == -1){
            int val = dfs_art_bridges(v, u, t);
            low = min(low, val);

            if (val >= num[u]) art[u]++;
            if (val > num[u]) bridge[idx] = 1;
        }
        else low = min(low, num[v]);
    }
    if (u == p && art[u]) art[u]--;
    return low;
}

void art_and_bridges(int n, int m, int one_indexed=1){
    num = vector<int>(n+1, -1);
    art = vector<int>(n+1, 0); // how many *new* 2cc if removed
    bridge = vector<int>(m+1, 0); // is bridge
    int t = 0;
    for (int i = one_indexed; i < n-one_indexed; i++) if (num[i] == -1)
        dfs_art_bridges(i, i, t);
}

vector<pair<int, int>> g2 [mx];
vector<int> comp (mx);

void dfs(int u, int c){
    comp[u] = c;
    for (auto [v, i]: g[u]){
        if (comp[v] || bridge[i]) continue;
        dfs(v, c);
    }
}

vector<char> ans (mx);
vector<int> val (mx), deg (mx), f (mx);

void solution(){
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edges;
    for (int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
        edges.push_back({a, b});
    }
    art_and_bridges(n, m);

    int c=1;
    for (int i=1; i<=n; i++) if (!comp[i]) dfs(i, c++);
    c--;

    for (int u=1; u<=n; u++) for (auto [v, i]: g[u]) if (bridge[i] && v < u){
        g2[comp[u]].push_back({comp[v], i});
        g2[comp[v]].push_back({comp[u], i});
    }

    queue<int> q;
    for (int i=1; i<=c; i++){
        deg[i] = sz(g2[i]);
        if (deg[i] == 1){
            q.push(i);
        }
    }

    int p;
    cin >> p;
    while (p--){
        int a, b;
        cin >> a >> b;
        val[comp[a]]++;
        val[comp[b]]--;
    }

    while (!q.empty()){
        int u = q.front(); q.pop();
        for (auto [v, i]: g2[u]){
            if (ans[i]) continue;

            val[v] += val[u];
            int o = (comp[edges[i].first] == u);
            if (!val[u]) ans[i] = 'B';
            else if ((val[u] > 0) == o) ans[i] = 'R';
            else ans[i] = 'L';

            deg[v]--;
            if (deg[v] == 1) q.push(v);
        }
    }

    for (int i=0; i<m; i++){
        cout << (bridge[i]? ans[i] : 'B');
    }
    cout << '\n';
}

signed main(){
    fastio;
    int cases=1;
    //cin >> cases;
    for (int i=0; i<cases; i++){
        solution();
    }
}

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