oj.uz

Submission #583267

# Submission time Handle Problem Language Result Execution time Memory
583267 2022-06-25T07:26:22 Z drdilyor One-Way Streets (CEOI17_oneway) C++17
0 / 100
 7 ms 8388 KB 
#if defined(ONPC) && !defined(_GLIBCXX_ASSERTIONS)
    #define _GLIBCXX_ASSERTIONS
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#ifdef ONPC
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())

using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K>
using ordered_set = pd::tree<K, pd::null_type, less<int>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T>
using gp_hash_table = pd::gp_hash_table<T...>;//simple using statement gives warnings

const int INF = 1e9;
const ll INFL = 1e18;
const int N = 1e5;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);

int solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n);
    vector<pair<int,int>> edges;

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
        edges.emplace_back(u, v);
    }

    vector<char> visited(n, false);
    vi tin(n, -1), low(n, -1);
    int timer = 0;
    vector<vi> bridge(n, vi(n, false));
    vector<vi> res(n, vi(n, 0));

    function<void(int,int)> dfs = [&](int v, int p) {
        visited[v] = true;
        tin[v] = low[v] = timer++;
        for (auto [to, _] : adj[v]) {
            if (to == p) continue;
            if (visited[to]) {
                low[v] = min(low[v], tin[to]);
            } else {
                dfs(to, v);
                low[v] = min(low[v], low[to]);
                if (low[to] > tin[v]) {
                    bridge[v][to] = true;
                    bridge[to][v] = true;
                }
            }
        }
    };

    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i, -1);
    }

    function<bool(int,int)> dfs2 = [&](int v, int dest) {
        if (v == dest) return true;
        if (visited[v]) return false;
        visited[v] = true;
        for (auto [e, _] : adj[v]) {
            if (dfs2(e, dest)) {
                if (bridge[v][e]) {
                    assert(res[v][e] != 2);
                    assert(res[e][v] != 1);
                    res[v][e] = 1;
                    res[e][v] = 2;
                }
                return true;
            }
        }
        return false;
    };
    int q; cin >> q;
    while (q--) {
        int from, to;
        cin >> from >> to;
        from--; to--;
        visited.assign(n, false);
        dfs2(from, to);
    }

    for (int i = 0; i < m; i++) {
        auto [u, v] = edges[i];
        if (u == v) cout << 'B';
        else if (res[u][v] == 1) cout << 'R';
        else if (res[u][v] == 2) cout << 'L';
        else cout << 'B';
    }
    return 0;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
#ifdef ONPC
    cin >> t;
#endif
    while (t-- && cin) {
        if (solve()) break;
        #ifdef ONPC
            cout << "____________________" << endl;
        #endif
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 4 ms 8276 KB Output is correct
5 Correct 7 ms 8388 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 5 ms 8276 KB Output is correct
8 Correct 5 ms 8276 KB Output is correct
9 Incorrect 3 ms 2260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 4 ms 8276 KB Output is correct
5 Correct 7 ms 8388 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 5 ms 8276 KB Output is correct
8 Correct 5 ms 8276 KB Output is correct
9 Incorrect 3 ms 2260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 4 ms 8276 KB Output is correct
5 Correct 7 ms 8388 KB Output is correct
6 Correct 2 ms 2388 KB Output is correct
7 Correct 5 ms 8276 KB Output is correct
8 Correct 5 ms 8276 KB Output is correct
9 Incorrect 3 ms 2260 KB Output isn't correct
10 Halted 0 ms 0 KB -