제출 #422056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422056		snasibov05	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	332 KiB

oneway

#include <iostream>
#include <vector>
#include <map>

using namespace std;

#define pb push_back
#define pii pair<int, int>
#define f first
#define s second

vector<vector<int>> ed;
map<pii, char> ans;
map<pii, bool> is_bridge;
map<pii, pii> bridge;
vector<int> ret;
vector<int> tin;
vector<int> cmp;
vector<bool> visited;
vector<int> sum;
int cur_t = 0;
int nxt = 1;


void findBridges(int cur, int pr){
    visited[cur] = true;
    tin[cur] = ++cur_t;
    ret[cur] = tin[cur];
    for (auto to : ed[cur]){
        if (to == pr || to == cur) continue;
        if (visited[to]) ret[cur] = min(ret[cur], tin[to]);
        else {
            findBridges(to, cur);
            ret[cur] = min(ret[cur], ret[to]);
        }

        if (ret[to] > tin[cur]) is_bridge[{cur, to}] = is_bridge[{to, cur}] = true;
    }
}

void dfs(int cur){
    visited[cur] = true;
    cmp[cur] = nxt;
    for (auto to : ed[cur]){
        if (!is_bridge[{cur, to}]) {
            if (!visited[to])dfs(to);
            ans[{cur, to}] = ans[{to, cur}] = 'B';
        } else if (!visited[to]){
            ++nxt;
            dfs(to);
        }
    }
}

void subtreeSum(int cur, int pr){
    for (auto to : ed[cur]){
        if (to == pr) continue;
        subtreeSum(to, cur);
        sum[cur] += sum[to];
    }
}

void calcAns(int cur, int pr){
    if (pr != -1){
        int u = bridge[{cur, pr}].f;
        int v = bridge[{cur, pr}].s;
        if (sum[cur] > 0) ans[{u, v}] = ans[{v, u}] = 'R';
        else ans[{u , v}] = ans[{v, u}] = 'L';
    }

    for (auto to : ed[cur]){
        if (to == pr) continue;
        calcAns(to, cur);
    }
}

void init(int n){
    ed.resize(n+1);
    tin.resize(n+1);
    ret.resize(n+1);
    cmp.resize(n+1);
    sum.resize(n+1);
    visited.resize(n+1);
}

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

    init(n);
    vector<pii> g(m);

    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[i].f = u; g[i].s = v;
        ed[u].pb(v);
        ed[v].pb(u);
    }

    findBridges(1, -1);
    visited.assign(n+1, false);
    dfs(1);

    vector<vector<int>> new_ed(n);
    for (int i = 1; i <= n; ++i) {
        for (auto to : ed[i]){
            if (cmp[i] == cmp[to]) continue;
            new_ed[cmp[i]].pb(cmp[to]);
            bridge[{cmp[i], cmp[to]}] = bridge[{cmp[to], cmp[i]}] = {i, to};
        }
    }

    for (int i = 1; i <= n; ++i) ed[i] = new_ed[i];

    int p; cin >> p;
    vector<pii> important(p);
    for (int i = 0; i < p; ++i) {
        cin >> important[i].f >> important[i].s;
        sum[cmp[important[i].f]]++;
        sum[cmp[important[i].s]]--;
    }

    subtreeSum(1, 0);
    calcAns(1, -1);

    for (int i = 0; i < m; ++i) {
        if (g[i].f == g[i].s) ans[{g[i].f, g[i].s}] = 'B';
        cout << ans[{g[i].f, g[i].s}];
    }


    return 0;
}

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