Submission #1322570

#TimeUsernameProblemLanguageResultExecution timeMemory
1322570vk3601hOne-Way Streets (CEOI17_oneway)C++20
100 / 100
107 ms22452 KiB
#include <bits/stdc++.h>
using namespace std;

class Solver{
private:
    //Graph
    int node_num, edge_num, query_num;
    vector<vector<tuple<int, int, bool>>> graph;

    //DFS Tree
    vector<vector<int>> dfs_tree;
    vector<int> root, depth, edge_id, dp, vals;
    vector<bool> edge_dir, vis_node, vis_edge;

    void build_dfs_tree(int curr){
        for (auto [child, edge, dir] : graph[curr]){
            if (!vis_node[child]){
                depth[child] = depth[curr] + 1;
                vis_node[child] = true;
                vis_edge[edge] = true;
                dfs_tree[curr].push_back(child);
                edge_id[child] = edge;
                edge_dir[child] = dir;
                build_dfs_tree(child);
            }
            else if (!vis_edge[edge]){
                vis_edge[edge] = true;
                int u = curr, v = child;
                if (depth[u] > depth[v]) swap(u, v);
                dp[u]--;
                dp[v]++;
            }
        }
    }

    void calc_dp(int curr){
        for (int child : dfs_tree[curr]) calc_dp(child);
        for (int child : dfs_tree[curr]) dp[curr] += dp[child];
    }

    void update_path(int u, int v){
        vals[u]++;
        vals[v]--;
    }

    void sum_up_vals(int curr){
        for (int child : dfs_tree[curr]) sum_up_vals(child);
        for (int child : dfs_tree[curr]) vals[curr] += vals[child];
    }

public:
    Solver() {
        cin >> node_num >> edge_num;

        graph.resize(node_num);
        for (int i = 0; i < edge_num; i++){
            int u, v;
            cin >> u >> v;
            u--, v--;
            graph[u].push_back({v, i, true});
            graph[v].push_back({u, i, false});
        }

        dfs_tree.resize(node_num);
        depth.resize(node_num, 0);
        edge_id.resize(node_num, 0);
        dp.resize(node_num, 0);
        vals.resize(node_num, 0);
        edge_dir.resize(node_num);
        vis_node.resize(node_num, false);
        vis_edge.resize(edge_num, false);

        for (int i = 0; i < node_num; i++){
            if (!vis_node[i]){
                root.push_back(i);
                vis_node[i] = true;
                build_dfs_tree(i);
            }
        }
        for (int rt : root) calc_dp(rt);

        cin >> query_num;
        while (query_num--){
            int u, v;
            cin >> u >> v;
            u--, v--;
            update_path(u, v);
        }
        for (int rt : root) sum_up_vals(rt);

        vector<char> ans(edge_num, 'B');
        for (int i = 0; i < node_num; i++){
            if (dp[i] == 0){
                char dir = 'B';
                if (vals[i] > 0) dir = edge_dir[i] ? 'L' : 'R';
                if (vals[i] < 0) dir = edge_dir[i] ? 'R' : 'L';
                ans[edge_id[i]] = dir;
            }
        }
        for (char dir : ans) cout << dir;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Solver();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...