Submission #904084

#TimeUsernameProblemLanguageResultExecution timeMemory
904084selmahbnOne-Way Streets (CEOI17_oneway)C++17
30 / 100
139 ms262144 KiB
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

const int INF = numeric_limits<int>::max() / 2;

vector<int> num, low, comp, used;
stack<int> s;
int dfs_count = 0;
int comp_count = 0;

vector<vector<int>> dir;
vector<int> in;
vector<int> out;

void tarjan_dfs(int current, int parent, vector<vector<pii>>& adj) {
    num[current] = low[current] = dfs_count;
    dfs_count++;
    s.push(current);
    for (pii neigh : adj[current]) {
        if (used[neigh.second] == 1) continue;
        used[neigh.second] = 1;
        if (num[neigh.first] == INF) {
            tarjan_dfs(neigh.first, current, adj);
            low[current] = min(low[current], low[neigh.first]);
        } else low[current] = min(low[current], num[neigh.first]);
    }
    if (num[current] == low[current]) {
        while (s.top() != current) {
            int top = s.top();
            s.pop();
            comp[top] = comp_count;
        }
        s.pop();
        comp[current] = comp_count;
        comp_count++;
    }
}

int dir_dfs(int current, vector<int>& visited, vector<vector<int>>& adj) {
    visited[current] = 1;
    int incoming = in[current] - out[current];
    for (int neigh : adj[current]) {
        if (visited[neigh] == 0) {
            int d = dir_dfs(neigh, visited, adj);
            if (d < 0) {
                dir[current][neigh] = -1;
                dir[neigh][current] = 1;
            } else if (d > 0) {
                dir[current][neigh] = 1;
                dir[neigh][current] = -1;
            }
            incoming += d;
        }
    }
    return incoming;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> adj(n);
    vector<pii> streets;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(make_pair(b, i));
        adj[b].push_back(make_pair(a, i));
        streets.push_back(make_pair(a, b));
    }
    num = vector<int>(n, INF);
    low = vector<int>(n);
    comp = vector<int>(n);
    used = vector<int>(m, 0);
    for (int i = 0; i < n; i++) {
        if (num[i] == INF) {
            tarjan_dfs(i, i, adj);
        }
    }
    vector<vector<int>> cadj(comp_count);
    for (pii s : streets) {
        if (comp[s.first] != comp[s.second]) {
            cadj[comp[s.first]].push_back(comp[s.second]);
            cadj[comp[s.second]].push_back(comp[s.first]);
        }
    }
    in = vector<int>(comp_count, 0);
    out = vector<int>(comp_count, 0);
    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (comp[a] != comp[b]) {
            out[comp[a]]++;
            in[comp[b]]++;
        }
    }
    vector<int> visited(comp_count, 0);
    dir = vector<vector<int>>(comp_count, vector<int>(comp_count, 0));
    for (int i = 0; i < comp_count; i++) {
        if (visited[i] == 0) dir_dfs(i, visited, cadj);
    }
    for (pii s : streets) {
        if (comp[s.first] == comp[s.second] || dir[comp[s.first]][comp[s.second]] == 0) cout << 'B';
        else if (dir[comp[s.first]][comp[s.second]] == 1) cout << 'R';
        else cout << 'L';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...