Submission #563714

#	Time	Username	Problem	Language	Result	Execution time	Memory
563714		generic_placeholder_name	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	196 ms	33868 KiB

oneway

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 1e5 + 5;
vi adj[N], g[N];
int l[N], r[N];
int ans[N];
int x[N], y[N];
bool is_bridge[N];

int disc[N], low[N];
void dfs(int u, int idp = -1) {
    static int t = 0;
    disc[u] = low[u] = ++t;
    for(int id: adj[u]) if(id != idp) {
        int v = l[id] + r[id] - u;
        if(disc[v]) low[u] = min(low[u], disc[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if(low[v] > disc[u]) is_bridge[id] = 1;
        }
    }
}

int d[N];
int grp[N];
int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
void join(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y]; d[y] = x;
}

constexpr int L = 17;
int pedge[N];
int par[N][L], lz[N][L];
int dep[N];

void dfs2(int u, int p) {
    rep1(i, L - 1) par[u][i] = par[par[u][i - 1]][i - 1];
    for(int id: g[u]) {
        int v = l[id] + r[id] - u;
        if(v != p) {
            pedge[v] = id;
            dep[v] = dep[u] + 1;
            par[v][0] = u;
            dfs2(v, u);
        }
    }
}

int lca(int u, int v) {
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = L - 1; ~i; i--) if(dep[v] - (1 << i) >= dep[u]) {
        v = par[v][i];
    }
    if(u == v) return u;
    for(int i = L - 1; ~i; i--) if(par[u][i] != par[v][i]) {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

void upd(int u, int v, int x) {
    for(int i = L - 1; ~i; i--) if(dep[u] - (1 << i) >= dep[v]) {
        lz[u][i] = x;
        u = par[u][i];
    }
}

int32_t main() {
    fastio;
    int n, m; cin >> n >> m;
    rep(i, m) {
        cin >> l[i] >> r[i]; --l[i], --r[i];
        adj[r[i]].pb(i);
        adj[l[i]].pb(i);
    }
    rep(i, n) if(!disc[i]) dfs(i);
    memset(d, -1, sizeof(d));
    memset(ans, -1, sizeof(ans));
    rep(i, m) if(!is_bridge[i]) join(l[i], r[i]);
    memset(grp, -1, sizeof(grp));
    int k = 0;
    rep(i, n) {
        int r = find(i);
        if(!~grp[r]) grp[r] = k++;
        grp[i] = grp[r];
    }
    rep(i, m) if(is_bridge[i]) {
        l[i] = grp[l[i]];
        r[i] = grp[r[i]];
        g[l[i]].pb(i);
        g[r[i]].pb(i);
    }
    memset(pedge, -1, sizeof(pedge));
    memset(par, -1, sizeof(par));
    memset(lz, -1, sizeof(lz));
    rep(i, k) if(!~par[i][0]) dfs2(i, i);
    int p; cin >> p;
    while(p--) {
        int x, y; cin >> x >> y; --x, --y;
        x = grp[x], y = grp[y];
        if(x == y) continue;
        int v = lca(x, y);
        upd(x, v, 1);
        upd(y, v, 0);
    }
    for(int i = L - 1; i; i--) {
        rep(u, k) if(~lz[u][i]) {
            lz[u][i - 1] = lz[u][i];
            lz[par[u][i - 1]][i - 1] = lz[u][i];
        }
    }
    rep(i, k) {
        int id = pedge[i];
        if(~lz[i][0]) {
            assert(id != -1);
            ans[id] = lz[i][0] ^ (i == l[id]);
        }
    }
    rep(i, m) cout << (!~ans[i] ? 'B' : ans[i] ? 'L' : 'R');
}

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