oj.uz

Submission #769762

# Submission time Handle Problem Language Result Execution time Memory
769762 2023-06-30T08:29:32 Z Blagoj One-Way Streets (CEOI17_oneway) C++17
100 / 100
 119 ms 38348 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 4 ms 8156 KB Output is correct
4 Correct 5 ms 8288 KB Output is correct
5 Correct 5 ms 8420 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 6 ms 8452 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 5 ms 8184 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 4 ms 8156 KB Output is correct
4 Correct 5 ms 8288 KB Output is correct
5 Correct 5 ms 8420 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 6 ms 8452 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 5 ms 8184 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 37 ms 13128 KB Output is correct
12 Correct 29 ms 14156 KB Output is correct
13 Correct 45 ms 15724 KB Output is correct
14 Correct 42 ms 20052 KB Output is correct
15 Correct 53 ms 21584 KB Output is correct
16 Correct 80 ms 32604 KB Output is correct
17 Correct 69 ms 34236 KB Output is correct
18 Correct 99 ms 32588 KB Output is correct
19 Correct 67 ms 35452 KB Output is correct
20 Correct 32 ms 14148 KB Output is correct
21 Correct 31 ms 13896 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Correct 4 ms 8156 KB Output is correct
4 Correct 5 ms 8288 KB Output is correct
5 Correct 5 ms 8420 KB Output is correct
6 Correct 4 ms 8148 KB Output is correct
7 Correct 6 ms 8452 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 5 ms 8184 KB Output is correct
10 Correct 4 ms 8148 KB Output is correct
11 Correct 37 ms 13128 KB Output is correct
12 Correct 29 ms 14156 KB Output is correct
13 Correct 45 ms 15724 KB Output is correct
14 Correct 42 ms 20052 KB Output is correct
15 Correct 53 ms 21584 KB Output is correct
16 Correct 80 ms 32604 KB Output is correct
17 Correct 69 ms 34236 KB Output is correct
18 Correct 99 ms 32588 KB Output is correct
19 Correct 67 ms 35452 KB Output is correct
20 Correct 32 ms 14148 KB Output is correct
21 Correct 31 ms 13896 KB Output is correct
22 Correct 89 ms 35388 KB Output is correct
23 Correct 89 ms 33748 KB Output is correct
24 Correct 119 ms 33844 KB Output is correct
25 Correct 76 ms 38348 KB Output is correct
26 Correct 96 ms 34932 KB Output is correct
27 Correct 98 ms 33932 KB Output is correct
28 Correct 31 ms 11272 KB Output is correct
29 Correct 46 ms 14796 KB Output is correct
30 Correct 53 ms 15076 KB Output is correct
31 Correct 49 ms 15392 KB Output is correct
32 Correct 57 ms 22616 KB Output is correct