Submission #896995

#	Time	Username	Problem	Language	Result	Execution time	Memory
896995		shmax	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	174 ms	55308 KiB

oneway

/*
 * powered by ANDRIY POPYK
 * in honor of MYSELF and SEGMENT DECOMPOSITION and N^(log(N)) and (Harry Potter and the Methods of Rationality) and Monkie D. Luffy
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report                                       \
    auto end = std::chrono::high_resolution_clock::now(); \
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
    { cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;

template<typename T>
vector<T> vect(int n, T val) {
    return vector<T>(n, val);
}

template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
    return vector<vector<T>>(n, vector<T>(m, val));
}

template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}

template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
    return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}

template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
    return matrix<T>(n, vector<T>(m, val));
}

template<typename T>
graph<T> new_graph(int n) {
    return graph<T>(n);
}

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

template<typename T>
using vec = vector<T>;

using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;

struct Bridges {
private:
    graph<pair<int, int>> g;
    vector<int> tin, fup;
    vector<bool> used;
    int timer;


    void build_dfs(int v, int p = -1, int edge_idx = -1) {
        used[v] = true;
        tin[v] = fup[v] = timer++;
        for (auto [u, id]: g[v]) {
            if (u == p) {
                continue;
            }
            if (used[u]) {
                fup[v] = min(fup[v], tin[u]);
            } else {
                build_dfs(u, v, id);
                fup[v] = min(fup[v], fup[u]);
            }
        }
        if (p != -1 and fup[v] > tin[p]) {
            is_bridge[edge_idx] = true;
            bridges.insert(edge_idx);
        }
    }

    void build_components_dfs(int v, int comp) {
        components[v] = comp;
        for (auto [u, id]: g[v]) {
            if (components[u] == -1 and !is_bridge[id]) {
                build_components_dfs(u, comp);
            }
        }
    }

public:
    set<int> bridges;
    vec<bool> is_bridge;
    vec<int> components;
    int components_count;
    graph<pair<int, int>> condensation;
    vec<pair<int, int>> edges;

    Bridges(graph<pII> &gt, int m) {
        g = gt;
        int idx = m;
        tin = fup = vector<int>(len(g));
        used = vector<bool>(len(g));
        timer = 0;
        is_bridge = vec<bool>(idx);
        for (int i = 0; i < len(g); ++i) {
            if (!used[i]) {
                build_dfs(i);
            }
        }
    }

    void build_components() {
        components = vec<int>(len(g), -1);
        components_count = 0;
        for (int i = 0; i < len(g); ++i) {
            if (components[i] == -1) {
                build_components_dfs(i, components_count++);
            }
        }
    }

    void build_condensation() {
        condensation = graph<pII>(components_count);
        vec<set<pair<int, int>>> edges_(components_count);
        for (int i = 0; i < len(g); ++i) {
            for (auto &to: g[i]) {
                if (components[i] != components[to.first]) {
                    edges_[components[i]].insert({components[to.first], to.second});
                }
            }
        }
        for (int i = 0; i < components_count; ++i) {
            for (auto &to: edges_[i]) {
                condensation[i].push_back(to);
            }
        }
    }

    void print_condensation() {
//        print edges of condensation
        for (int i = 0; i < components_count; ++i) {
            for (auto [u, id]: condensation[i]) {
                cout << i << " " << u << " " << id << endl;
            }
        }
    }
};

struct state {
public:
    int left_f, right_f;
    int left_s, right_s;

    state &operator=(state _val) {
        this->left_f = _val.left_f;
        this->right_f = _val.right_f;
        this->left_s = _val.left_s;
        this->right_s = _val.right_s;
        return *this;
    }
};
template<typename T>
struct option {
    T val;
    bool is_empty;

    option() : is_empty(true) {}

    option(T val) : val(val), is_empty(false) {}

    option<T> &operator=(T _val) {
        this->val = _val;
        this->is_empty = false;
        return *this;
    }

    option<T> &operator=(option<T> _val) {
        this->val = _val;
        this->is_empty = false;
        return *this;
    }

    T operator*() {
        if (is_empty) {
            throw runtime_error("option is none");
        }
        return val;
    }


    bool operator==(option<T> _val) {
        if (is_empty and _val.is_empty) {
            return true;
        }
        if (is_empty or _val.is_empty) {
            return false;
        }
        return val == _val.val;
    }

    bool operator!=(option<T> _val) {
        return !(*this == _val);
    }

    bool is_some() {
        return !is_empty;
    }

    bool is_none() {
        return is_empty;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    graph<pII> g(n);
    vec<pII> edges(m);
    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].emplace_back(u, i);
        g[u].emplace_back(v, i);
        edges[i] = {v, u};
    }
    Bridges b(g, m);
    b.build_components();
    b.build_condensation();
    vec<char> ans(m,'B');
    for (int i = 0; i < m; i++) {
        if (!b.is_bridge[i]) {
            ans[i] = 'B';
        }
    }
    int p;
    cin >> p;
    vec<pair<int, int>> queries;
    while (p--) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        v = b.components[v];
        u = b.components[u];
        queries.emplace_back(v, u);
    }
    int dn = b.components_count;
//    b.print_condensation();
    vec<int> alias(dn, -1);
    vec<pII> sub_tree(dn);
    int cnt = 0;
    function<void(int)> build_alias = [&](int v) {
        alias[v] = cnt++;
        sub_tree[v] = {alias[v], alias[v]};
        for (auto [u, id]: b.condensation[v]) {
            if (alias[u] == -1) {
                build_alias(u);
            }
        }
        sub_tree[v].second = cnt - 1;
    };


    vec<option<state>> dp(dn);

    vec<int> to_finish_left(dn);
    vec<int> to_finish_right(dn);
    vec<int> to_start_left(dn);
    vec<int> to_start_right(dn);
    for (int i = 0; i < dn; ++i) {
        if (alias[i] == -1) {
            build_alias(i);
        }
    }

    for (int i = 0; i < dn; i++) {
        to_finish_left[i] = to_finish_right[i] = to_start_left[i] = to_start_right[i] = alias[i];
    }

    for (auto [v, u]: queries) {
        chmin(to_finish_left[v], alias[u]);
        chmax(to_finish_right[v], alias[u]);
        chmin(to_start_left[u], alias[v]);
        chmax(to_start_right[u], alias[v]);
    }

    function<void(int, int, int)> dfs = [&](int v, int p, int id = -1) {
        if (dp[v].is_some())
            return;
        state cur = {to_finish_left[v], to_finish_right[v], to_start_left[v], to_start_right[v],};
        for (auto [u, uid]: b.condensation[v]) {
            if (u == p)
                continue;
            dfs(u, v, uid);
            if (dp[u].is_some()) {
                state s = *dp[u];
                chmin(cur.left_f, s.left_f);
                chmin(cur.left_s, s.left_s);
                chmax(cur.right_f, s.right_f);
                chmax(cur.right_s, s.right_s);
            }
        }
        dp[v] = cur;
        if (id != -1) {
            ans[id] = 'B';
            if (sub_tree[v].first > cur.left_f or sub_tree[v].second < cur.right_f) {
                if (b.components[edges[id].first] != p)
                    ans[id] = 'R';
                else
                    ans[id] = 'L';
            }
            if (sub_tree[v].first > cur.left_s or sub_tree[v].second < cur.right_s) {
                if (b.components[edges[id].first] != p)
                    ans[id] = 'L';
                else
                    ans[id] = 'R';
            }
        }
    };


    for (int i = 0; i < dn; ++i) {
        if (dp[i].is_none()) {
            dfs(i, -1, -1);
        }
    }
    for (int i = 0; i < m; ++i) {
        cout << ans[i];
    }


}

Compilation message (stderr)

oneway.cpp: In member function 'void Bridges::build_dfs(long long int, long long int, long long int)':
oneway.cpp:158:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |         for (auto [u, id]: g[v]) {
      |                   ^
oneway.cpp: In member function 'void Bridges::build_components_dfs(long long int, long long int)':
oneway.cpp:177:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  177 |         for (auto [u, id]: g[v]) {
      |                   ^
oneway.cpp: In member function 'void Bridges::print_condensation()':
oneway.cpp:236:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  236 |             for (auto [u, id]: condensation[i]) {
      |                       ^
oneway.cpp: In lambda function:
oneway.cpp:352:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  352 |         for (auto [u, id]: b.condensation[v]) {
      |                   ^
oneway.cpp: In function 'int main()':
oneway.cpp:377:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  377 |     for (auto [v, u]: queries) {
      |               ^
oneway.cpp: In lambda function:
oneway.cpp:388:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  388 |         for (auto [u, uid]: b.condensation[v]) {
      |                   ^

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