Submission #841601

#	Time	Username	Problem	Language	Result	Execution time	Memory
841601		treewave	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	604 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    map<array<int, 2>, char> ans;

    vector<vector<int>> adj(n, vector<int>());
    vector<array<int, 2>> edges(m);
    for (int i = 0; i < m; i++){
        cin >> edges[i][0] >> edges[i][1];
        edges[i][0]--; edges[i][1]--;
        if (edges[i][0] != edges[i][1]){
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
        }
        else{
            ans[edges[i]] = 'B';
        }
    }
    int p; cin >> p;
    vector<vector<int>> out(n), in(n);
    for (int i = 0; i < p; i++){
        int u, v; cin >> u >> v; u--; v--;
        if (u == v) continue;
        out[u].push_back(v);
        in[v].push_back(u);
    }

    vector<bool> vis(n, false);

    vector<vector<int>> out_back_edges(n), in_back_edges(n);
    vector<vector<int>> main_tree(n);

    int time = 0;
    vector<int> tin(n, -1), tout(n, -1);

    auto dfs_tree = [&](auto self, int u, int parent) -> void{
        vis[u] = true;
        tin[u] = time++;
        for (int v : adj[u]){
            if (v == parent) continue;
            if (!vis[v]){
                main_tree[u].push_back(v);
                main_tree[v].push_back(u);
                self(self, v, u);
            }
            else{
                if (tout[v] != -1){
                    //meaning v is a descendant
                    in_back_edges[u].push_back(v);
                    out_back_edges[v].push_back(u);
                }
                ans[{u, v}] = 'B';
                ans[{v, u}] = 'B';
            }
        }
        tout[u] = time++;
    };

    int out_p_active = 0, in_p_active = 0;
    int active_back_edges = 0;

    auto dfs = [&](auto self, int u, int v) -> void{
        for (int node : main_tree[u]){
            if (node != v){
                self(self, node, u);
            }
        }
        if (v == 0){
            in_p_active = 0;
            out_p_active = 0;
            active_back_edges = 0;
        }
        active_back_edges += out_back_edges[u].size();
        active_back_edges -= in_back_edges[u].size();
        for (int node : out[u]){
            if (tin[u] <= tin[node] && tout[node] <= tout[u]){
                in_p_active--;
            }
            else{
                out_p_active++;
            }
        }
        for (int node : in[u]){
            if (tin[u] <= tin[node] && tout[node] <= tout[u]){
                out_p_active--;
            }
            else{
                in_p_active++;
            }
        }
//        cerr << "u, v: " << u << " " << v << " backedges = " << active_back_edges << " in_p_active: " << in_p_active << " out_p_active: " << out_p_active << endl;
        if (active_back_edges > 0){
            ans[{u, v}] = 'B';
            ans[{v, u}] = 'B';
        }
        else{
            //we found a bridge
            assert(!(in_p_active > 0 && out_p_active > 0));
            if (in_p_active > 0){
                ans[{u, v}] = 'L';
                ans[{v, u}] = 'R';
            }
            else{
                if (out_p_active > 0){
                    ans[{u, v}] = 'R';
                    ans[{v, u}] = 'L';
                }
                else{
                    ans[{u, v}] = 'B';
                    ans[{v, u}] = 'B';
                }
            }
        }
    };


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

            out_p_active = 0; in_p_active = 0;
            active_back_edges = 0; time = 0;
        }
    }

    for (int i = 0; i < m; i++){
        cout << ans[edges[i]];
    }
    cout << "\n";
}

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