Submission #878711

#	Time	Username	Problem	Language	Result	Execution time	Memory
878711		Ghulam_Junaid	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	2648 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, p, h[N], mnh[N], st[N], ft[N], tme;

bool vis[N];
vector<pair<int, int>> g[N], edges, important;
string s;

bool in_sub(int u, int v){
    return (st[v] <= st[u] && st[u] <= ft[v]);
}

void dfs(int v, int prev = -1){
    vis[v] = 1;
    mnh[v] = h[v];

    st[v] = tme;
    tme++;

    // cout << "Running dfs on " << v << endl;

    for (auto [id, u] : g[v]){
        if (id == prev) continue;

        if (!vis[u]){
            h[u] = h[v] + 1;
            dfs(u, id);
            mnh[v] = min(mnh[v], mnh[u]);

            if (mnh[u] > h[v]){ // (v, u) is a bridge
                // cout << v << " -- " << u << " is a bridge." << endl;
                for (auto [x, y] : important){
                    bool A = in_sub(x, u);
                    bool B = in_sub(y, u);

                    // cout << x << " " << y << " " << u << " " << A << " " << B << endl;

                    if (A and !B){
                        // u to v
                        if (edges[id].first == u)
                            s[id] = 'R';
                        else
                            s[id] = 'L';

                        break;
                    }
                    if (!A and B){
                        // v to u
                        if (edges[id].first == v)
                            s[id] = 'R';
                        else
                            s[id] = 'L';

                        break;
                    }
                }
            }
        }
        else
            mnh[v] = min(mnh[v], h[u]);
    }
    ft[v] = tme;
}

int main(){
    cin >> n >> m;

    for (int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;

        g[u].push_back({i, v});
        g[v].push_back({i, u});
        edges.push_back({u, v});

        s += 'B';
    }

    cin >> p;
    for (int i=0; i<p; i++){
        int u, v;
        cin >> u >> v;

        important.push_back({u, v});
    }

    dfs(1);

    cout << s << endl;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40