Submission #583738

#	Time	Username	Problem	Language	Result	Execution time	Memory
583738		drdilyor	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	380 ms	46096 KiB

oneway

#if defined(ONPC) && !defined(_GLIBCXX_ASSERTIONS)
    #define _GLIBCXX_ASSERTIONS
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#ifdef ONPC
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())

using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K>
using ordered_set = pd::tree<K, pd::null_type, less<int>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T>
using gp_hash_table = pd::gp_hash_table<T...>;//simple using statement gives warnings

const int INF = 1e9;
const ll INFL = 1e18;
const int N = 1e5;
const int LOGN = 17;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);

struct LCA {
    int n;
    vi parent[LOGN];
    vi parentedgeix;
    vi depth;

    LCA(vector<vector<pair<int,int>>>& adj) {
        n = sz(adj);
        depth = vi(n, -1);
        parentedgeix = vi(n, -1);
        for (int i = 0; i < LOGN; i++) parent[i] = vi(n, -1);
        for (int i = 0; i < n; i++)
            if (depth[i] == -1)
                dfs(adj, i);
        for (int j = 1; j < LOGN; j++) {
            for (int i = 0; i < n; i++) {
                if (parent[j-1][i] != -1)
                    parent[j][i] = parent[j-1][ parent[j-1][i] ];
            }
        }
    }
    void dfs(vector<vector<pair<int,int>>>& adj, int i, int p = -1) {
        if (p ==-1) depth[i] = 0;
        for (auto [e, edgeix] : adj[i]) if (e != p) {
            depth[e] = depth[i]+1;
            parent[0][e] = i;
            parentedgeix[e] = edgeix;
            dfs(adj, e, i);
        }
    }
    int query(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        for (int j = LOGN-1; j >= 0; j--) {
            if (parent[j][a] == -1) continue;
            if (depth[parent[j][a]] >= depth[b])
                a = parent[j][a];
        }
        if (a == b) return a;
        for (int j = LOGN-1; j>= 0; j--) {
            if (parent[j][a] != -1 && parent[j][b] != -1
             && parent[j][a] != parent[j][b]) {
                a = parent[j][a];
                b = parent[j][b];
            }
        }
        return parent[0][a];
    }
};

int solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n);
    vector<pair<int,int>> edges;
    set<pair<int,int>> edgeSet;
    set<pair<int,int>> neverBridge;

    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);
        edges.emplace_back(u, v);

        pair<int,int> key = {min(u, v), max(u, v)};
        if (edgeSet.count(key)) {
            neverBridge.insert(key);
        }
        edgeSet.insert(key);
    }

    vector<char> visited(n, false);
    vi tin(n, -1), low(n, -1);
    int timer = 0;
    set<pair<int,int>> bridges;

    function<void(int,int)> dfs = [&](int v, int p) {
        visited[v] = true;
        tin[v] = low[v] = timer++;
        for (auto [to, _] : adj[v]) {
            if (to == p) continue;
            if (visited[to]) {
                low[v] = min(low[v], tin[to]);
            } else {
                dfs(to, v);
                low[v] = min(low[v], low[to]);
                if (low[to] > tin[v]) {
                    pair<int,int> key = {min(to, v), max(to, v)};
                    if (neverBridge.count(key)) continue;
                    bridges.insert(key);
                }
            }
        }
    };

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

    vector<vector<pair<int,int>>> ccadj;
    vi rootof(n, -1);
    int roots = 0;
    
    function<void(int, int)> dfsCC = [&](int i, int root) {
        if (rootof[i] != -1) return;
        rootof[i] = root;
        for (auto [e, edgeix] : adj[i]) {
            if (bridges.count({min(i,e), max(i,e)}) == 0) {
                dfsCC(e, root);
            } else {
                if (rootof[e] == -1) {
                    roots++;
                    ccadj.resize(ccadj.size()+1);
                    dfsCC(e, roots-1);
                }
                ccadj[root].emplace_back(rootof[e], edgeix);
            }
        }
    };
    for (int i = 0; i < n; i++) {
        if (rootof[i] == -1) {
            roots++;
            ccadj.resize(ccadj.size()+1);
            dfsCC(i, roots-1);
        }
    }

    debug(rootof, ccadj);
    LCA lca(ccadj);
    string res(edges.size(), 'B');
    int q; cin >> q;
    vector<pair<int,int>> pathUp, pathDown;
    while (q--) {
        int from, to;
        cin >> from >> to;
        from = rootof[from-1], to = rootof[to-1];
        int c = lca.query(from, to);
        assert(c != -1);
        pathUp.emplace_back(from, c);
        pathDown.emplace_back(to, c);
    }
    auto comp = [&](pair<int,int> a, pair<int,int> b) { return a.second < b.second; };
    sort(allit(pathUp), comp);
    sort(allit(pathDown), comp);
    for (auto [from, c] : pathUp) {
        while (from != c) {
            int eix = lca.parentedgeix[from];
            if (res[max(eix, ~eix)] != 'B') break;
            if (eix < 0) res[~eix] = 'R';
            else res[eix] = 'L';
            from = lca.parent[0][from];
        }
    }
    for (auto [to, c] : pathDown) {
        while (to != c) {
            int eix = lca.parentedgeix[to];
            if (res[max(eix, ~eix)] != 'B') break;
            if (eix < 0) res[~eix] = 'L';
            else res[eix] = 'R';
            to = lca.parent[0][to];
        }
    }
    cout << res;
    
    return 0;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
#ifdef ONPC
    cin >> t;
#endif
    while (t-- && cin) {
        if (solve()) break;
        #ifdef ONPC
            cout << "____________________" << endl;
        #endif
    }
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int solve()':
oneway.cpp:10:24: warning: statement has no effect [-Wunused-value]
   10 |     #define debug(...) 42
      |                        ^~
oneway.cpp:159:5: note: in expansion of macro 'debug'
  159 |     debug(rootof, ccadj);
      |     ^~~~~

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