Submission #1293201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293201		chaoslong	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	2 ms	332 KiB

oneway

// Calm down.
// Think three times, code twice.
#include "bits/stdc++.h"
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353
const ll oo = 1e18;

int n, m, p, low[N], num[N], par[N], color[N], timer = 0, scc = 0, h[N], p2[N], tin[N], head[N], heavy[N], res[N], euler[N];
stack<int> s;
bool deleted[N];
vector<pii> a[N], g[N];
char ans[N];
pii f[N], tmp[N];

void dfs(int u, int pre) {
    num[u] = low[u] = ++timer;
    s.push(u);
    for(pii e: a[u]) {
        int v = e.st, cur = e.nd;
        if(deleted[v] || cur == pre) continue;
        if(!num[v]) {
            par[v] = u;
            dfs(v, cur);
            low[u] = min(low[u], low[v]);
        } else low[u] = min(low[u], num[v]);
    }
//    cout << u << " " << num[u] << " " << low[u] << "\n";
    if(low[u] == num[u]) {
        scc++;
        int v;
        do {
            v = s.top();
            s.pop();
            deleted[v] = 1;
            color[v] = scc;
        } while(v != u);
    }
}

int dfs2(int u, int pre) {
    int sz = 0, mx = 0;
    for(pii e: g[u]) {
        int v = e.st;
        if(v == pre) continue;
        h[v] = h[u] + 1;
        p2[v] = u;
        int cur = dfs2(v, u);
        if(cur > mx) {
            mx = cur;
            heavy[u] = v;
        }
        sz += cur;
    }
    return sz;
}

void hld(int u, int cur) {
    tin[u] = ++timer;
    euler[timer] = u;
    head[u] = cur;
    if(heavy[u]) {
        hld(heavy[u], cur);
    }
    for(pii e: g[u]) {
        int v = e.st;
        if(v == p2[u] || v == heavy[u]) continue;
        hld(v, v);
    }
}

struct seg {
    vector<int> t, lazy;
    int n;
    void init(int _n) {
        n = _n;
        t.assign(4 * n + 5, 0);
        lazy.assign(4 * n + 5, 0);
    }

    void push_down(int id, int l, int r, int mid) {
        if(!lazy[id]) return;
        int val = lazy[id]; lazy[id] = 0;
        t[id << 1] = t[id << 1 | 1] = lazy[id << 1] = lazy[id << 1 | 1] = val;
    }

    void update(int id, int l, int r, int u, int v, int val) {
        if(l > v || r < u || l > r || u > v) return;
        if(u <= l && r <= v) {
            t[id] = val;
            lazy[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        push_down(id, l, r, mid);
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }

    void down(int id, int l, int r) {
        if(l == r) {
//            cout << l << " " << t[id] << "\n";
            res[euler[l]] = t[id];
            return;
        }
        int mid = (l + r) >> 1;
        push_down(id, l, r, mid);
        down(id << 1, l, mid);
        down(id << 1 | 1, mid + 1, r);
    }

    void update(int u, int v, int val) {
        update(1, 1, n, u, v, val);
    }
} it;

void update(int u, int v) {
    while(head[u] != head[v]) {
        if(tin[head[u]] < tin[head[v]]) {
            it.update(tin[head[v]], tin[v], 2);
            v = p2[head[v]];
        } else {
            it.update(tin[head[u]], tin[u], 1);
            u = p2[head[u]];
        }
    }
    if(tin[u] < tin[v]) {
        it.update(tin[u] + 1, tin[v], 2);
    } else {
        it.update(tin[v] + 1, tin[u], 1);
    }
}

void dfs3(int u, int pre) {
    for(pii e: g[u]) {
        int v = e.st, id = e.nd;
        if(v == pre) continue;
        dfs3(v, u);
//        cout << u << " " << v << " " << res[v] << "\n";
        if(res[v] == 1) {
            int l = v, r = u;
            if(l == tmp[id].st && r == tmp[id].nd) {
                ans[id] = 'R';
            } else {
                ans[id] = 'L';
            }
        } else if(res[v] == 2) {
            int l = u, r = v;
            if(l == tmp[id].st && r == tmp[id].nd) {
                ans[id] = 'R';
            } else {
                ans[id] = 'L';
            }
        } else {
            ans[id] = 'B';
        }
    }
}

void to_nho_cau() {
    cin >> n >> m;
    forr(i, 1, m) {
        int u, v; cin >> u >> v;
        a[u].pb({v, i});
        a[v].pb({u, i});
        f[i].st = u; f[i].nd = v;
    }
    dfs(1, 0);
//    forr(i, 1, n) cout << color[i] << " ";
    forr(i, 1, m) {
        int u = color[f[i].st], v = color[f[i].nd];
        if(u != v) {
            g[u].pb({v, i});
            g[v].pb({u, i});
            tmp[i] = {u, v};
//            cout << u << " " << v << "\n";
        } else {
//            cout << i << "\n";
            ans[i] = 'B';
        }
    }
    timer = 0;
    dfs2(1, 0);
    hld(1, 1);
    it.init(timer);
    cin >> p;
    forr(i, 1, p) {
        int u, v; cin >> u >> v;
        u = color[u], v = color[v];
//        cout << u << " " << v << "\n";
        update(u, v);
    }
    it.down(1, 1, timer);
//    forr(i, 1, n) cout << res[i] << " "; cout << "\n";
    dfs3(1, 0);
    forr(i, 1, m) cout << ans[i];
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef LOCAL
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) to_nho_cau();
}
/*
1.self check:
2.long long
3.size of array
4.code for testing
5.initializing
6.modulo number
*/
/**
 ∧__∧
（｀•ω• )づ__∧
（つ　 /( •ω•。)
  しーＪ (nnノ) pat pat
**/
/**  /\_/\
*   (= ._.)
*   / >☕ \>💻
**/

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