Submission #585064

#	Time	Username	Problem	Language	Result	Execution time	Memory
585064		tengiz05	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	990 ms	262144 KiB

oneway

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> adj(n);
    vector<vector<pair<int, int>>> ADJ(n);
    
    map<pair<int, int>, int> id, ID;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
        ADJ[u].emplace_back(v, 0);
        ADJ[v].emplace_back(u, 1);
        ID[minmax(u, v)] = i;
    }
    
    vector<int> in(n), f(n), c(n);
    
    int timeStamp = 0;
    
    vector<bool> vis(n);
    stack<int> st;
    int S = 0;
    function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = f[u] = timeStamp++;
        vis[u] = true;
        st.push(u);
        for (auto [v, i] : adj[u]) {
            if (!vis[v]) {
                dfs(v, i);
                f[u] = min(f[u], f[v]);
            } else if (i != p) {
                f[u] = min(f[u], f[v]);
            }
        }
        if (f[u] == in[u]) {
            int x;
            do {
                x = st.top();
                st.pop();
                c[x] = S;
            } while (x != u);
            S++;
        }
    };
    
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs(i, -1);
        }
    }
    
    // for (int i = 0; i < n; i++) {
        // cout << c[i] << " \n"[i == n - 1];
    // }
    
    vector<vector<pair<int, int>>> e(n);
    for (int u = 0; u < n; u++) {
        for (auto [v, x] : ADJ[u]) {
            if (c[u] != c[v]) {
                e[c[u]].emplace_back(c[v], x);
                id[minmax(c[u], c[v])] = ID[minmax(u, v)];
                // cerr << c[u] << " : " << c[v]  << "\n";
            }
        }
    }
    
    vector<vector<int>> ev(n);
    
    int p;
    cin >> p;
    
    vector<int> U(p + 1), V(p + 1);
    
    for (int i = 1; i <= p; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        if (c[u] == c[v])
            continue;
        ev[c[u]].push_back(i);
        ev[c[v]].push_back(-i);
    }
    
    vector<int> ans(m, -1);
    
    vis.assign(n, 0);
    
    set<int> s[n];
    
    function<void(int, int, int)> dfs2 = [&](int u, int p, int d) {
        vis[u] = true;
        for (int x : ev[u]) {
            s[u].insert(x);
        }
        for (auto [v, x] : e[u]) {
            if (vis[v]) assert(v == p);
            if (!vis[v]) {
                dfs2(v, u, x);
                for (int g : s[v]) {
                    if (s[u].count(-g)) {
                        s[u].erase(-g);
                    } else {
                        s[u].insert(g);
                    }
                }
            }
        }
        if (p != -1 && !s[u].empty()) {
            ans[id[minmax(p, u)]] = d ^ (*s[u].begin() > 0);
        }
    };
    
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs2(i, -1, -1);
        }
    }
    
    for (int i = 0; i < m; i++) {
        if (ans[i] == 0) {
            cout << "R";
        } else if (ans[i] == 1) {
            cout << "L";
        } else {
            cout << "B";
        }
    }
    
    return 0;
}
/*

5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3

3 2
1 2
2 3

2
3 1
3 1

*/

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40