Submission #1224850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224850		minhtan1103	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	63 ms	28856 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define pt pair<int, int>
const int maxN = 1e5 + 5;

int n, m, p, tplt, dem;
vector<pt> adj[maxN], edge;
set<int> comp[maxN];
int num[maxN], low[maxN], scc[maxN];
int dis[maxN], val[maxN];
stack<int> st;

void tarjan(int u, int pre_id){
    num[u] = low[u] = ++dem;
    st.push(u);
    for (pt e : adj[u]){
        int v = e.first;
        int cur_id = e.second;
        if (cur_id == pre_id) continue;
        if (num[v]) low[u] = min(low[u], num[v]);
        else{
            tarjan(v, cur_id);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] == num[u]){
        ++tplt;
        int v;
        do{
            v = st.top();
            scc[v] = tplt;
            st.pop();
        } while(u != v);
    }
}

void dfs(int u, int pre){
    for (int v : comp[u]){
        if (v == pre) continue;
        dis[v] = dis[u] + 1;
        dfs(v, u);
        val[u] += val[v];
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int a, b; cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edge.push_back({a, b});
    }
    for (int i = 1; i <= n; ++i){
        if (!num[i]) tarjan(i, 0);
    }
    cin >> p;
    for (int i = 1; i <= p; ++i){
        int u, v; cin >> u >> v;
        u = scc[u];
        v = scc[v];
        ++val[u];
        --val[v];
    }
    for (pt e : edge){
        int u = scc[e.first];
        int v = scc[e.second];
        if (u == v) continue;
        comp[u].insert(v);
        comp[v].insert(u);
    }
    for (int i = 1; i <= tplt; ++i){
        if (!dis[i]) dfs(i, 0);
    }
    for (pt e : edge){
        int u = scc[e.first];
        int v = scc[e.second];
        if (u == v) cout << "B";
        if (dis[u] > dis[v]){
            if (val[u] == 0) cout << "B";
            if (val[u] > 0) cout << "R";
            if (val[u] < 0) cout << "L";
        }
        if (dis[u] < dis[v]){
            if (val[v] == 0) cout << "B";
            if (val[v] > 0) cout << "L";
            if (val[v] < 0) cout << "R";
        }
    }

    return 0;
}

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