Submission #769762

#	Time	Username	Problem	Language	Result	Execution time	Memory
769762		Blagoj	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	119 ms	38348 KiB

oneway

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

vector<int> g[100005];
stack<int> s;
unordered_set<int> cgr[100005];
int Time = 0, scc = 0, id[100005], tim[100005], low[100005], val[100005], dist[100005];
bool ins[100005];

void tarjan(int n, int p) {
    tim[n] = low[n] = ++Time;
    s.push(n);
    ins[n] = 1;
    for (auto x : g[n]) {
        if (x == p) {
            p = -1;
            continue;
        }
        if (tim[x] == 0) {
            tarjan(x, n);
            low[n] = min(low[n], low[x]);
        }
        else if (ins[x]) low[n] = min(low[n], tim[x]);
    }
    if (tim[n] == low[n]) {
        while (s.top() != n) {
            id[s.top()] = scc;
            ins[s.top()] = 0;
            s.pop();
        }
        id[s.top()] = scc;
        ins[s.top()] = 0;
        s.pop();
        scc++;
    }
}

void dfs(int n, int p) {
    for (auto x : cgr[n]) {
        if (x == p) continue;
        dist[x] = dist[n] + 1;
        dfs(x, n);
        val[n] += val[x];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    int f[m], t[m];
    for (int i = 0; i < m; i++) {
        cin >> f[i] >> t[i];
        g[f[i]].push_back(t[i]);
        g[t[i]].push_back(f[i]);
    }
    for (int i = 1; i <= n; i++) if (!tim[i]) tarjan(i, -1);
    for (int i = 0; i < m; i++) {
        if (id[f[i]] != id[t[i]]) {
            cgr[id[f[i]]].insert(id[t[i]]);
            cgr[id[t[i]]].insert(id[f[i]]);
        }
    }
    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        val[id[a]]++;
        val[id[b]]--;
    }
    for (int i = 0; i < scc; i++) if (dist[i] == 0) dfs(i, -1);
    for (int i = 0; i < m; i++) {
        int a = id[f[i]], b = id[t[i]];
        if (a == b) cout << "B";
        if (dist[a] > dist[b]) {
            if (val[a] > 0) cout << "R";
            if (val[a] == 0) cout << "B";
            if (val[a] < 0) cout << "L";
        }
        if (dist[a] < dist[b]) {
            if (val[b] > 0) cout << "L";
            if (val[b] == 0) cout << "B";
            if (val[b] < 0) cout << "R";
        }
    }
}

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