제출 #1332148

#제출 시각아이디문제언어결과실행 시간메모리
1332148algoproclubOne-Way Streets (CEOI17_oneway)C++20
0 / 100
1 ms344 KiB
// UUID: 2004e116-88e1-4514-baca-c29cd69772ab
#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 (vissza[pos] == eler[pos]){
        if (cnt == 0) mo[pos] = 'B';
        else 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){
            mo[i] = '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...