Submission #926387

#TimeUsernameProblemLanguageResultExecution timeMemory
926387RegulusOne-Way Streets (CEOI17_oneway)C++17
30 / 100
74 ms69740 KiB
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 1e5+5;
const int LogN = 17;
int dfn[N], low[N], timer, tag[LogN+5][N], tin[N],
    tout[N], anc[LogN+5][N];
pll e[N];
bool cut[N];
vector<pll> g[N];
vector<int> tr[N];

inline void tarjan(int x, int pid)
{
    dfn[x] = low[x] = ++timer;
    for (auto e : g[x])
    {
        int v = e.F, id = e.S;
        if (id == pid) continue;
        if (!dfn[v])
        {
            tarjan(v, id);
            tr[x].pb(v), tr[v].pb(x);
            low[x] = min(low[x], low[v]);
        } else {
            low[x] = min(low[x], dfn[v]);
        }
        if (low[v] > dfn[x]) cut[id] = 1;
    }
}

inline bool is_anc(int x, int y)
{ return tin[x] < tin[y] && tout[y] < tout[x]; }

inline void dfs(int x, int pre)
{
    tin[x] = ++timer, anc[0][x] = pre;
    for (int v : tr[x]) if (v != pre) dfs(v, x);
    tout[x] = ++timer;
}

inline int get_lca(int x, int y)
{
    if (is_anc(x, y)) return x;
    if (is_anc(y, x)) return y;
    for (int i=LogN; i >= 0; --i)
        if (anc[i][x] && !is_anc(anc[i][x], y)) x = anc[i][x];
    return anc[0][x];
}

inline void update(int x, int y, int c)
{
    for (int i=LogN; i >= 0; --i)
    {
        if (anc[i][x] && !is_anc(anc[i][x], y))
            tag[i][x] |= c, x = anc[i][x];
    }
}

int main(void)
{ IO
    int n, i, m, Q;
    
    cin >> n >> m;
    for (i=1; i <= m; ++i)
    {
        int x, y; cin >> x >> y, e[i] = {x, y};
        g[x].pb(y, i), g[y].pb(x, i);
    }
    
    for (i=1; i <= n; ++i)
    {
        if (!dfn[i])
        {
            tarjan(i, 0);
            dfs(i, 0);
        }
    }
    for (i=1; i <= LogN; ++i)
        for (int j=1; j <= n; ++j) anc[i][j] = anc[i-1][anc[i-1][j]];
    
    cin >> Q;
    do {
        int x, y; cin >> x >> y;
        int tmp = get_lca(x, y);
        update(x, tmp, 1), update(y, tmp, 2);
    } while (--Q);
    for (i=LogN; i > 0; --i)
    {
        for (int j=1; j <= n; ++j)
        {
            tag[i-1][j] |= tag[i][j];
            tag[i-1][anc[i-1][j]] |= tag[i][j];
        }
    }
    
    for (i=1; i <= m; ++i)
    {
        if (!cut[i]) cout << "B";
        else {
            int x = e[i].F, y = e[i].S;
            if (x == y) continue;
            if (tin[x] < tin[y]) swap(x, y);
            if (tag[0][x] == 3) assert(0);
            if (tag[0][x] == 1)
            {
                if (x == e[i].F) cout << "R";
                else cout << "L";
            } else if (tag[0][x] == 2) {
                if (x == e[i].F) cout << "L";
                else cout << "R";
            } else {
                cout << "B";
            }
        }
    }
    cout << '\n';


    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...