Submission #1332153

#TimeUsernameProblemLanguageResultExecution timeMemory
1332153algoproclubOne-Way Streets (CEOI17_oneway)C++20
0 / 100
0 ms344 KiB
// UUID: d9bc139d-aa8f-4e9c-9284-2d806801725e
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int> > > graph;
vector<int> eler, vissza, db;
int ido = 1;
vector<char> mo;

int dfs(int pos, int parI){
    eler[pos] = ido;
    vissza[pos] = ido++;
    int cnt = db[pos];
    for (pair<int, int> x : graph[pos]){
        if (x.second == -parI) continue;
        if (eler[x.first]) {
            vissza[pos] = min(vissza[pos], eler[x.first]);
        }
        else {
            cnt += dfs(x.first, x.second);
            vissza[pos] = min(vissza[pos], vissza[x.first]);
        }
    }
    if (pos && vissza[pos] == eler[pos]){
        if (cnt != 0){
            if ((cnt > 0) xor (parI > 0)){
                mo[abs(parI)] = 'R';
            }
            else mo[abs(parI)] = 'L';
        }
    }
    return cnt;
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n);
    mo.resize(m + 1, 'B');
    eler.resize(n);
    vissza.resize(n);
    db.resize(n);
    for (int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (a == b){
            continue;
        }
        graph[a].push_back({b, i});
        graph[b].push_back({a, -i});
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        db[a]++;
        db[b]--;
    }
    dfs(0, 0);
    for (int i = 1; i <= m; i++) cout << mo[i];
    cout << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...