oj.uz

Submission #467291

# Submission time Handle Problem Language Result Execution time Memory
467291 2021-08-22T12:22:57 Z idk321 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 357 ms 38468 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
vector<array<int, 2>> adj[N];
vector<array<int, 2>> adj2[N];
bool isBridge[N];
int up[N];
int in[N];
int out[N];
int timer;
int n, m;
int group[N];
array<int, 2> par[N];
int goNext[N];
array<int, 2> direction[N];
map<array<int, 2>, int> groupEdgeToNode;

void bridges(int node, array<int, 2> par) {
    in[node] = timer++;
    up[node] = in[node];

    for (auto next : adj[node]) {
        if (next[0] == par[0]) continue;
        if (in[next[0]]) {
            up[node] = min(up[node], in[next[0]]);
        } else {
            bridges(next[0], {node, next[1]});
            up[node] = min(up[node], up[next[0]]);
        }
    }

    if (node != 1 && up[node] == in[node]) {
        isBridge[par[1]] = true;
    }
}

void clean() {
    for (int i = 0; i <= n; i++) {
        up[i] = 0;
        in[i] = 0;
    }
    for (int i = 0; i <= m; i++) {
        isBridge[i] = false;
    }
    timer = 1;
}

void assignGroup(int node, int cgroup) {
    group[node] = cgroup;
    for (auto next : adj[node]) {
        if (!group[next[0]] && !isBridge[next[1]]) {
            assignGroup(next[0], cgroup);
        }
    }
}


void dfs(int node, array<int, 2> p) {

    in[node] = ++timer;
    par[node] = p;
    for (auto next : adj2[node]) {
        if (next == p) continue;
        dfs(next[0], {node, next[1]});
    }

    out[node] = timer;
}

void query(int node, int other, bool first) {
    if (goNext[node] != node) {
        query(goNext[node], other, first);
        goNext[node] = goNext[goNext[node]];
    } else {
        if (in[node] <= in[other] && out[other] <= out[node]) {

        } else {
            if (first) {
                direction[par[node][1]] = {groupEdgeToNode[{node, par[node][0]}], groupEdgeToNode[{par[node][0], node}]};

            } else {
                direction[par[node][1]] = {groupEdgeToNode[{par[node][0], node}], groupEdgeToNode[{node, par[node][0]}]};
            }
            query(goNext[par[node][0]], other, first);
            goNext[node] = goNext[par[node][0]];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    vector<array<int, 2>> edgeNodes(m);
    for (int i = 0;  i< m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edgeNodes[i] = {a, b};
    }

    timer = 1;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) bridges(i, {-1, -1});
    }
    string res(m, 'B');
    int cgroup = 1;
    for (int i = 1; i <= n; i++) {
        if(!group[i]) assignGroup(i, cgroup++);
    }


    for (int i = 1; i <= n; i++) {
        for (auto next : adj[i]) {
            if (group[i] != group[next[0]]) {
                groupEdgeToNode[{group[i], group[next[0]]}] = i;
                adj2[group[i]].push_back({group[next[0]], next[1]});
            }
        }
    }
    clean();
    for (int i = 1; i <= n; i++) {
        array<int, 2> compareArray = {0, 0};
        if (par[i] == compareArray) dfs(i, {-1, -1});
    }

    for (int i = 0; i <N; i++) goNext[i] = i;

    int p;
    cin >> p;
    for (int p1 = 0; p1 < p; p1++) {
        int x, y;
        cin >> x >> y;
        if (group[x] != group[y]) {
            query(group[x], group[y], true);
            query(group[y], group[x], false);
        }
    }

    for (int i = 0; i < m; i++) {
        array<int, 2> compareArray = {0, 0};
        if (direction[i] != compareArray) {
            if (direction[i] == edgeNodes[i]) res[i] = 'R';
            else res[i] = 'L';
        }
    }
    cout << res << "\n";
}

/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 5 ms 5580 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Correct 6 ms 5580 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 4 ms 5452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 5 ms 5580 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Correct 6 ms 5580 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 4 ms 5452 KB Output is correct
11 Correct 45 ms 11840 KB Output is correct
12 Correct 63 ms 12952 KB Output is correct
13 Correct 74 ms 14688 KB Output is correct
14 Correct 89 ms 18628 KB Output is correct
15 Correct 124 ms 20112 KB Output is correct
16 Correct 137 ms 29976 KB Output is correct
17 Correct 169 ms 32068 KB Output is correct
18 Correct 149 ms 30612 KB Output is correct
19 Correct 169 ms 33164 KB Output is correct
20 Correct 53 ms 12868 KB Output is correct
21 Correct 53 ms 13448 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 5 ms 5580 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Correct 6 ms 5580 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 4 ms 5452 KB Output is correct
11 Correct 45 ms 11840 KB Output is correct
12 Correct 63 ms 12952 KB Output is correct
13 Correct 74 ms 14688 KB Output is correct
14 Correct 89 ms 18628 KB Output is correct
15 Correct 124 ms 20112 KB Output is correct
16 Correct 137 ms 29976 KB Output is correct
17 Correct 169 ms 32068 KB Output is correct
18 Correct 149 ms 30612 KB Output is correct
19 Correct 169 ms 33164 KB Output is correct
20 Correct 53 ms 12868 KB Output is correct
21 Correct 53 ms 13448 KB Output is correct
22 Correct 289 ms 33268 KB Output is correct
23 Correct 357 ms 31620 KB Output is correct
24 Correct 286 ms 31872 KB Output is correct
25 Correct 304 ms 38468 KB Output is correct
26 Correct 268 ms 33384 KB Output is correct
27 Correct 291 ms 31700 KB Output is correct
28 Correct 39 ms 9708 KB Output is correct
29 Correct 72 ms 13584 KB Output is correct
30 Correct 74 ms 13956 KB Output is correct
31 Correct 74 ms 14020 KB Output is correct
32 Correct 134 ms 21412 KB Output is correct