oj.uz

답안 #422114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422114 2021-06-09T17:55:45 Z snasibov05 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 142 ms 262148 KB 
#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, int k){
    visited[cur] = true;
    cmp[cur] = k;
    for (auto to : ed[cur]){
        if (!is_bridge[{cur, to}]) {
            if (!visited[to]) dfs(to, k);
            ans[{cur, to}] = ans[{to, cur}] = 'B';
        } else if (!visited[to]) dfs(to, nxt++);
    }
}

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

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

    for (auto to : ed[cur]){
        if (!visited[to]) 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);
    }

    for (int i = 1; i <= n; ++i){
        if (!visited[i]) findBridges(i, -1);
    }
    visited.assign(n+1, false);
    for (int i = 1; i <= n; ++i){
        if (!visited[i]) dfs(i, nxt++);
    }

    vector<vector<int>> new_ed(n+1);
    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]}] = {i, to};
            bridge[{cmp[to], cmp[i]}] = {to, i};
        }
    }

    ed = new_ed;

    int p; cin >> p;
    for (int i = 0; i < p; ++i) {
        int u, v; cin >> u >> v;
        sum[cmp[u]]++;
        sum[cmp[v]]--;
    }



    visited.assign(n+1, false);
    for (int i = 1; i <= n; ++i){
        if (!visited[i]) subtreeSum(i, -1);
    }
    visited.assign(n+1, false);
    for (int i = 1; i <= n; ++i){
        if (!visited[i]) calcAns(i, -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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 142 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -