Submission #1362621

#TimeUsernameProblemLanguageResultExecution timeMemory
1362621njoopOne-Way Streets (CEOI17_oneway)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

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

void dfs(int no, int rt, int dis) {
    vis[no] = 1;
    d[no] = dis;
    for(auto i: g[no]) {
        if(i == rt) continue;
        if(vis[i] == 1) {
            int u = no, v = i;
            if(d[no] > d[i]) swap(u, v);
            cnt[u]--;
            cnt[i]++;
        } else {
            dfs(i, no, dis+1);
            cnt[no] += cnt[i];
            qu[no] += qu[i];
        }
    }
    if(cnt[no] == 0) {
        auto [u, v, idx] = edge[{min(no, rt), max(no, rt)}];
        if(qu[no] > 0) {
            if(v == rt) ans[idx] = 'R';
            else ans[idx] = 'L';
        } else if(qu[no] < 0) {
            if(v == rt) ans[idx] = 'L';
            else ans[idx] = 'R';
        }
    }

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, p;
    cin >> n >> m;
    g.assign(n+2, vector<int>());
    vis.assign(n+2., 0);
    qu.assign(n+2, 0);
    cnt.assign(n+2, 0);
    d.assign(n+2, 0);
    ans.assign(n+2, 'B');
    for(int i=1; i<=m; i++) {
        int u, v;
        cin >> u >> v;
        pair<int, int> e = {min(u, v), max(u, v)};
        edge[e] = {u, v, i};
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> p;
    for(int i=1; i<=p; i++) {
        int u, v;
        cin >> u >> v;
        qu[u]++;
        qu[v]--;
    }
    dfs(1, -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...