Submission #1223728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223728		VMaksimoski008	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	109 ms	14660 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n, m, in[N], low[N], timer = 1, sum[N], q, b[N], c[N];
vector<array<int, 2> > g[N], edg(N);

void dfs(int u, int p) {
    in[u] = low[u] = timer++;
    for(auto [v, id] : g[u]) {
        if(p == id) continue;
        if(in[v]) {
            low[u] = min(low[u], in[v]);
        } else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if(low[v] > in[u]) b[id] = 1;

            if(sum[v] == 0) c[id] = 0;
            else if(sum[v] > 0) c[id] = 1;
            else c[id] = -1;

            if(edg[id][0] == u) c[id] *= 1;
            else c[id] *= -1;

            sum[u] += sum[v];
        }
    }
}

signed main() {
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back({ v, i });
        g[v].push_back({ u, i });
        edg[i] = { u, v };
    }

    cin >> q;
    while(q--) {
        int u, v; cin >> u >> v;
        sum[u]++;
        sum[v]--;
    }

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

    for(int i=1; i<=m; i++) {
        if(!b[i] || !c[i]) cout << 'B';
        else cout << (c[i] == 1 ? 'L' : 'R');
    }
}

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