제출 #1332161

#제출 시각아이디문제언어결과실행 시간메모리
1332161algoproclubOne-Way Streets (CEOI17_oneway)C++20
100 / 100
119 ms13108 KiB
// UUID: d125bf84-3924-4d7f-a57e-3e045782c596
#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] && 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.assign(n, 0);
    vissza.assign(n, 0);
    db.assign(n, 0);
    int a, b;
    for (int i = 1; i <= m; i++){
        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++){
        cin >> a >> b;
        a--, b--;
        db[a]++;
        db[b]--;
    }
    for (int i = 0; i < n; i++){
        if (!eler[i]) dfs(i, 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...