Submission #1096583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096583		f0rizen	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	70 ms	21048 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, ind;
};

vector<vector<Edge>> g;
vector<bool> used;
vector<int> d, up;
vector<bool> br;

void dfs_bridges(int v, int depth = 0, int p = -1) {
    used[v] = 1;
    d[v] = up[v] = depth;
    for (auto [u, ind] : g[v]) {
        if (!used[u]) {
            dfs_bridges(u, depth + 1, ind);
            up[v] = min(up[v], up[u]);
            if (d[v] < up[u]) {
                br[ind] = true;
            }
        } else if (ind != p) {
            up[v] = min(up[v], d[u]);
        }
    }
}

vector<int> c;

void dfs_color(int v, int cl) {
    c[v] = cl;
    for (auto [u, ind] : g[v]) {
        if (c[u] == -1 && !br[ind]) {
            dfs_color(u, cl);
        }
    }
}

vector<vector<int>> t;
vector<int> sum;

void dfs_sum(int v, int p = -1) {
    used[v] = 1;
    for (auto u : t[v]) {
        if (u != p) {
            d[u] = d[v] + 1;
            dfs_sum(u, v);
            sum[v] += sum[u];
        }
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m;
    cin >> n >> m;
    g.resize(n);
    vector<pair<int, int>> edg(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        edg[i] = {u, v};
    }
    used.resize(n);
    d.resize(n);
    up.resize(n);
    br.resize(m);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs_bridges(i);
        }
    }
    c.resize(n, -1);
    int cl = 0;
    for (int i = 0; i < n; ++i) {
        if (c[i] == -1) {
            dfs_color(i, cl++);
        }
    }
    t.resize(cl);
    for (int i = 0; i < m; ++i) {
        if (br[i]) {
            auto [u, v] = edg[i];
            t[c[u]].push_back(c[v]);
            t[c[v]].push_back(c[u]);
        }
    }
    int p;
    cin >> p;
    sum.resize(cl);
    for (int i = 0; i < p; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        ++sum[c[u]];
        --sum[c[v]];
    }
    used.clear();
    used.resize(cl);
    d.clear();
    d.resize(cl);
    for (int i = 0; i < cl; ++i) {
        if (!used[i]) {
            dfs_sum(i);
        }
    }
    for (auto [u, v] : edg) {
        int a = c[u], b = c[v];
        if (a == b) {
            cout << "B";
        } else if (d[a] > d[b]) {
            if (sum[a] > 0) {
                cout << "R";
            } else if (sum[a] < 0) {
                cout << "L";
            } else {
                cout << "B";
            }
        } else {
            if (sum[b] > 0) {
                cout << "L";
            } else if (sum[b] < 0) {
                cout << "R";
            } else {
                cout << "B";
            }
        }
    }
    cout << "\n";
    return 0;
}

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