oj.uz

답안 #422120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422120 2021-06-09T18:06:54 Z snasibov05 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 994 ms 73612 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;
map<pii, int> cnt;
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] && cnt[{to, cur}] == 1) 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){
    visited[cur] = true;
    for (auto to : ed[cur]){
        if (visited[to]) continue;
        subtreeSum(to);
        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;
        cnt[{u, v}]++;
        cnt[{v, u}]++;
        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};
        }
    }

    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);
    }
    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
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 5 ms 844 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 5 ms 972 KB Output is correct
8 Correct 4 ms 844 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 540 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 5 ms 844 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 5 ms 972 KB Output is correct
8 Correct 4 ms 844 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 540 KB Output is correct
11 Correct 603 ms 44580 KB Output is correct
12 Correct 582 ms 46648 KB Output is correct
13 Correct 621 ms 49324 KB Output is correct
14 Correct 702 ms 54556 KB Output is correct
15 Correct 818 ms 56464 KB Output is correct
16 Correct 895 ms 65248 KB Output is correct
17 Correct 869 ms 67728 KB Output is correct
18 Correct 968 ms 65304 KB Output is correct
19 Correct 827 ms 69448 KB Output is correct
20 Correct 599 ms 46912 KB Output is correct
21 Correct 519 ms 44984 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 5 ms 844 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 5 ms 972 KB Output is correct
8 Correct 4 ms 844 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 540 KB Output is correct
11 Correct 603 ms 44580 KB Output is correct
12 Correct 582 ms 46648 KB Output is correct
13 Correct 621 ms 49324 KB Output is correct
14 Correct 702 ms 54556 KB Output is correct
15 Correct 818 ms 56464 KB Output is correct
16 Correct 895 ms 65248 KB Output is correct
17 Correct 869 ms 67728 KB Output is correct
18 Correct 968 ms 65304 KB Output is correct
19 Correct 827 ms 69448 KB Output is correct
20 Correct 599 ms 46912 KB Output is correct
21 Correct 519 ms 44984 KB Output is correct
22 Correct 939 ms 68804 KB Output is correct
23 Correct 947 ms 66400 KB Output is correct
24 Correct 994 ms 66400 KB Output is correct
25 Correct 861 ms 73612 KB Output is correct
26 Correct 937 ms 68156 KB Output is correct
27 Correct 889 ms 66324 KB Output is correct
28 Correct 197 ms 5060 KB Output is correct
29 Correct 624 ms 47448 KB Output is correct
30 Correct 613 ms 47400 KB Output is correct
31 Correct 668 ms 48080 KB Output is correct
32 Correct 685 ms 47340 KB Output is correct