oj.uz

Submission #872592

# Submission time Handle Problem Language Result Execution time Memory
872592 2023-11-13T12:11:38 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 27068 KB 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define ONLINE_JUDGE
void solve() {
    int n, m;
    cin >> n >> m;

    map <pair <int, int>, int> mp;
    vector <pair <int, int>> adj[n +1];
    vector <pair <int, int>> edges(m);
    for(int i = 0; i < m; i++) {
        cin >> edges[i].first >> edges[i].second;
        adj[edges[i].first].emplace_back(edges[i].second, i);
        adj[edges[i].second].emplace_back(edges[i].first, i);
        mp[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}]++;
    }

    int timer = 0;
    vector <int> tin(n +1, -1), low(n +1, -1), is_bridge(m);
    function <void(int, int)> dfs = [&](int node, int par) -> void {
        low[node] = tin[node] = timer++;
        for(auto [child, number] : adj[node]) {
            if(child == par) {
                continue;
            }

            if(tin[child] == -1) {
                dfs(child, node);
                low[node] = min(low[node], low[child]);
                if(low[child] > tin[node]) {
                    //cerr << node << " " << child << " :: " << number << "\n";
                    is_bridge[number] = true;
                }
            } else {
                low[node] = min(low[node], tin[child]);
            }
        }
    };

    for(int i = 1; i <= n; i++) {
        if(tin[i] == -1) {
            dfs(i, -1);
        }
    }

    string res(m, 'B');
    for(int i = 0; i < m; i++) {
        if(mp[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}] > 1) {
            //cerr << edges[i].first << " " << edges[i].second << " :: " << i << "\n";
            is_bridge[i] = false;
        }

        if(is_bridge[i]) {
            res[i] = 'X';
        }
    }

    //cerr << res << "\n";

    vector <int> compo(n +1, -1);
    function <void(int, int)> dfsC = [&](int node, int color) {
        compo[node] = color;
        for(auto [child, num] : adj[node]) {
            if(compo[child] == -1 && !is_bridge[num]) {
                dfsC(child, color);
            }
        }
    };

    int col = 0;
    for(int i = 1; i <= n; i++) {
        if(compo[i] == -1) {
            dfsC(i, col);
            col++;
        }
    }

    /*
    for(int i = 1; i <= n; i++) {
        cerr << compo[i] << " \n"[i == n];
    }
    */

    vector <pair <int, int>> nadj[col +1];
    for(int i = 0; i < m; i++) {
        if(is_bridge[i]) {
            //cerr << i << " -> " << edges[i].first << " " << edges[i].second << " :: " << compo[edges[i].first] << " " << compo[edges[i].second] << "\n";
            nadj[compo[edges[i].first]].emplace_back(compo[edges[i].second], i);
            nadj[compo[edges[i].second]].emplace_back(compo[edges[i].first], i);
        }
    }

    vector <int> boya(m +1);
    function <bool(int, int, int)> DFS = [&](int node, int par, int ulas) -> bool {
        //cerr << node << " " << par << " " << ulas << "\n";
        if(node == ulas) {
            return true;
        }

        for(auto [child, num] : nadj[node]) {
            if(child == par) 
                continue;
            if(DFS(child, node, ulas)) {
                if(compo[edges[num].first] == node) {
                    boya[num] = 1;
                } else {
                    boya[num] = 2;
                }

                return true;
            }
        }

        return false;
    };

    int p;
    cin >> p;

    for(int i = 1; i <= p; i++) {
        int a, b;
        cin >> a >> b;
        //cerr << a << " " << b << " :: " << compo[a] << " " << compo[b] << "\n";
        DFS(compo[a], -1, compo[b]);
    }

    for(int i = 0; i < m; i++) {
        if(boya[i] == 1) {
            assert(res[i] == 'X');
            res[i] = 'R';
        } else if(boya[i] == 2) {
            assert(res[i] == 'X');
            res[i] = 'L';
        }
    }

    for(int i = 0; i < m; i++) {
        if(res[i] == 'X') {
            res[i] = 'B';
        }
    }

    cout << res;
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 456 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 99 ms 14676 KB Output is correct
12 Correct 87 ms 15952 KB Output is correct
13 Correct 96 ms 17748 KB Output is correct
14 Correct 109 ms 19740 KB Output is correct
15 Correct 123 ms 20428 KB Output is correct
16 Correct 109 ms 22896 KB Output is correct
17 Correct 224 ms 26544 KB Output is correct
18 Correct 187 ms 22864 KB Output is correct
19 Correct 296 ms 26900 KB Output is correct
20 Correct 93 ms 15708 KB Output is correct
21 Correct 72 ms 15192 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 99 ms 14676 KB Output is correct
12 Correct 87 ms 15952 KB Output is correct
13 Correct 96 ms 17748 KB Output is correct
14 Correct 109 ms 19740 KB Output is correct
15 Correct 123 ms 20428 KB Output is correct
16 Correct 109 ms 22896 KB Output is correct
17 Correct 224 ms 26544 KB Output is correct
18 Correct 187 ms 22864 KB Output is correct
19 Correct 296 ms 26900 KB Output is correct
20 Correct 93 ms 15708 KB Output is correct
21 Correct 72 ms 15192 KB Output is correct
22 Execution timed out 3008 ms 27068 KB Time limit exceeded
23 Halted 0 ms 0 KB -