Submission #489487

#	Time	Username	Problem	Language	Result	Execution time	Memory
489487		danielliu04	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	158 ms	21928 KiB

oneway

// Link: https://cses.fi/problemset/task/1691

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define lc (node<<1)+1
#define rc (node<<1)+2
#define endl '\n'
#define INF 1e9

const int max_n = 1e5+2;
int n, m, k;

pair<int, int> edges[max_n];
vector<int> adj[max_n];

int enter[max_n], low[max_n];
int t = 0;

int scc[max_n]; // stores the id of the strongly connected component
int id = 0;
stack<int> s;

vector<int> tree[max_n];
int dp[max_n];

void dfs(int node, int parent = -1){
    enter[node] = low[node] = t ++;
    s.push(node);

    bool pp = 0;
    for(int next : adj[node]){
        if(next != parent || pp){
            if(enter[next] == -1){
                dfs(next, node);
                low[node] = min(low[node], low[next]);
                if(low[next] == enter[next]){ // no edge going up 
                    while(true){
                        int a = s.top();
                        scc[a] = id;
                        s.pop();
                        if(a == next) break;
                    }
                    id ++;
                }
            }
            else{
                low[node] = min(low[node], enter[next]);
            }
        }
        else{
            pp = 1;
        }
    }
}

int depth[max_n];

void dfs2(int node, int parent = -1, int dep = 0){
    depth[node] = dep;
    for(int next: tree[node]){
        if(next == parent) continue;
        dfs2(next, node, dep + 1);
        dp[node] += dp[next];
    }
}

int main() {
    
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int a, b; cin >> a >> b; a --; b --;
        adj[a].push_back(b); adj[b].push_back(a);
        edges[i] = {a, b};
    }

    // find 2-edge-connected-components and create a tree out of it
    // always direct the edges from top->bottom

    fill(enter, enter + n, -1);
    for(int i = 0; i < n; i ++){
        if(enter[i] == -1){
            dfs(i);
            while(!s.empty()){
                int a = s.top();
                s.pop();
                scc[a] = id;
            }
            id ++;
        }
    }


    for(int i = 0; i < m; i ++){
        int a = scc[edges[i].first], b = scc[edges[i].second];
        if(a == b) continue;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    // now we loop through the required passages and assign values
    cin >> k;
    for(int i = 0; i < k; i ++){
        int a, b; cin >> a >> b; a --; b --;
        a = scc[a]; b = scc[b];
        dp[a]++; dp[b]--; // positive means going up, negative means going down
    }

    for(int i = 0; i < id; i ++){
        if(!depth[i]) dfs2(i);
    }

    for(int i = 0; i < m; i ++){
        int a = scc[edges[i].first], b = scc[edges[i].second];
        if(a == b) cout << 'B';
        else if(depth[b] > depth[a]){ // this means a is above b
            if(dp[b] < 0){
                cout << 'R';
            }
            else if(dp[b] == 0){
                cout << 'B';
            }
            else if(dp[b] > 0){
                cout << 'L';
            }
        }
        else{
            if(dp[a] < 0){
                cout << 'L';
            }
            else if(dp[a] == 0){
                cout << 'B';
            }
            else if(dp[a] > 0){
                cout << 'R';
            }
        }
    }

    cout << endl;
}   

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