Submission #1362628

#TimeUsernameProblemLanguageResultExecution timeMemory
1362628njoopOne-Way Streets (CEOI17_oneway)C++20
100 / 100
61 ms19780 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int, int>>> g;
map<pair<int, int>, tuple<int, int, int>> edge;
vector<int> vis, qu, d, cnt, eu, ev;
vector<char> ans;

void dfs(int no, int rt, int dis) {
    vis[no] = 1;
    d[no] = dis;
    for(auto [i, idx]: g[no]) {
        if(idx == rt) continue;
        if(vis[i] == 1) {
            if(d[no] > d[i]) {
                cnt[no]++;
                cnt[i]--;
            }
        } else {
            dfs(i, idx, dis+1);
            cnt[no] += cnt[i];
            qu[no] += qu[i];
        }
    }
    if(rt != -1 && cnt[no] == 0) {
        if(qu[no] > 0) {
            if(d[eu[rt]] > d[ev[rt]]) ans[rt] = 'R';
            else ans[rt] = 'L';
        } else if(qu[no] < 0) {
            if(d[eu[rt]] > d[ev[rt]]) ans[rt] = 'L';
            else ans[rt] = 'R';
        }
    }

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, p;
    cin >> n >> m;
    g.assign(n+2, vector<pair<int, int>>());
    vis.assign(n+2., 0);
    qu.assign(n+2, 0);
    cnt.assign(n+2, 0);
    d.assign(n+2, 0);
    ans.assign(m+2, 'B');
    eu.assign(m+2, 0);
    ev.assign(m+2, 0);
    for(int i=1; i<=m; i++) {
        int u, v;
        cin >> u >> v;
        eu[i] = u;
        ev[i] = v;
        pair<int, int> e = {min(u, v), max(u, v)};
        edge[e] = {u, v, i};
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    cin >> p;
    for(int i=1; i<=p; i++) {
        int u, v;
        cin >> u >> v;
        qu[u]++;
        qu[v]--;
    }
    for(int i=1; i<=n; i++) {
        if(vis[i] == 0) dfs(i, -1, 0);
    }
    for(int i=1; i<=m; i++) {
        cout << ans[i];
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...