oj.uz

Submission #872841

# Submission time Handle Problem Language Result Execution time Memory
872841 2023-11-13T23:41:39 Z MisterReaper One-Way Streets (CEOI17_oneway) C++17
100 / 100
 161 ms 27452 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";

    queue <int> q;
    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);
            } else if(compo[child] == -1) {
                q.emplace(child);
            }
        }
    };

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

        while(!q.empty()) {
            int x = q.front();
            q.pop();
            if(compo[x] != -1)
                continue;
            
            dfsC(x, col);
            col++;
        }
    }

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

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

    int p;
    cin >> p;

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

    vector <int> vis(col);
    function <void(int)> DFS = [&](int node) -> void {
        vis[node] = true;
        for(auto [child, num] : nadj[node]) {
            if(!vis[child])
                DFS(child);
            val[node] += val[child];
        }
    };

    for(int i = 0; i < col; i++) {
        if(!vis[i]) {
            DFS(i);
        }
    }

    for(int i = 0; i < m; i++) {
        if(res[i] == 'X') {
            int x = compo[edges[i].first], y = compo[edges[i].second];
            //cerr << edges[i].first << " " << edges[i].second << " :: " << x << " " << y << " -> " << val[x] << " " << val[y] << "\n";
            if(x < y) {
                if(val[y] > 0)
                    res[i] = 'L';
                else if(val[y] < 0)
                    res[i] = 'R';
                else
                    res[i] = 'B';
            } else if(x > y) {
                if(val[x] > 0)
                    res[i] = 'R';
                else if(val[x] < 0)
                    res[i] = 'L';
                else
                    res[i] = 'B';
            } else {
                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 460 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 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 348 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 460 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 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 348 KB Output is correct
11 Correct 94 ms 14504 KB Output is correct
12 Correct 87 ms 16088 KB Output is correct
13 Correct 94 ms 17748 KB Output is correct
14 Correct 108 ms 19792 KB Output is correct
15 Correct 107 ms 19872 KB Output is correct
16 Correct 126 ms 21276 KB Output is correct
17 Correct 102 ms 23376 KB Output is correct
18 Correct 114 ms 21320 KB Output is correct
19 Correct 110 ms 24400 KB Output is correct
20 Correct 83 ms 15444 KB Output is correct
21 Correct 74 ms 14676 KB Output is correct

Subtask #3
40.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 460 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 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 348 KB Output is correct
11 Correct 94 ms 14504 KB Output is correct
12 Correct 87 ms 16088 KB Output is correct
13 Correct 94 ms 17748 KB Output is correct
14 Correct 108 ms 19792 KB Output is correct
15 Correct 107 ms 19872 KB Output is correct
16 Correct 126 ms 21276 KB Output is correct
17 Correct 102 ms 23376 KB Output is correct
18 Correct 114 ms 21320 KB Output is correct
19 Correct 110 ms 24400 KB Output is correct
20 Correct 83 ms 15444 KB Output is correct
21 Correct 74 ms 14676 KB Output is correct
22 Correct 161 ms 24344 KB Output is correct
23 Correct 118 ms 22608 KB Output is correct
24 Correct 127 ms 22608 KB Output is correct
25 Correct 111 ms 27452 KB Output is correct
26 Correct 108 ms 23892 KB Output is correct
27 Correct 116 ms 22740 KB Output is correct
28 Correct 40 ms 5180 KB Output is correct
29 Correct 91 ms 16032 KB Output is correct
30 Correct 102 ms 16212 KB Output is correct
31 Correct 96 ms 17016 KB Output is correct
32 Correct 90 ms 19028 KB Output is correct