제출 #1327800

#제출 시각아이디문제언어결과실행 시간메모리
1327800kawhietOne-Way Streets (CEOI17_oneway)C++20
0 / 100
3028 ms5228 KiB
#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5 + 1;

bool vis[N];
multiset<int> g[N];

void dfs(int u) {
    vis[u] = 1;
    for (auto v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        g[a[i]].insert(b[i]);
        g[b[i]].insert(a[i]);
    }
    int k;
    cin >> k;
    vector<int> x(k), y(k);
    for (int i = 0; i < k; i++) {
        cin >> x[i] >> y[i];
    }
    auto good = [&]() {
        for (int i = 0; i < k; i++) {
            fill(vis, vis + n + 1, false);
            dfs(x[i]);
            if (!vis[y[i]]) {
                return false;
            }
        }
        return true;
    };
    string ans(m, ' ');
    for (int i = 0; i < m; i++) {
        int u = a[i], v = b[i];
        g[u].erase(g[u].find(v));
        bool l = good();
        g[u].insert(v);
        g[v].erase(g[v].find(u));
        bool r = good();
        g[v].insert(u);
        if (l && r) {
            ans[i] = 'B';
        } else if (l) {
            ans[i] = 'L';
        } else {
            ans[i] = 'R';
        }
    }
    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...