Submission #350201

#	Time	Username	Problem	Language	Result	Execution time	Memory
350201		12tqian	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	1182 ms	52380 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; i++)
#define f0r(i, a) f1r(i, 0, a)
#define trav(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

template <class T> struct SparseTable {
    std::vector<T> v;
    std::vector<std::vector<int>> jump;

    int level(int x) {
        return 31 - __builtin_clz(x);
    }

    int comb(int a, int b) {
        return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
    }

    void init(const std::vector<T>& _v) {
        v = _v;
        jump = {std::vector<int>((int) v.size())};
        iota(jump[0].begin(), jump[0].end(), 0);
        for (int j = 1; (1 << j) <= (int) v.size(); j++) {
            jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1));
            for (int i = 0; i < (int) jump[j].size(); i++) {
                jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    int index(int l, int r) {
        assert(l <= r);
        int d = level(r - l + 1);
        return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
    }

    T query(int l, int r) {
        return v[index(l, r)];
    }
};

struct LCAJump {
    int n;
    std::vector<std::vector<int>> par;
    std::vector<std::vector<int>> adj;
    std::vector<int> depth;

    void init(int _n) {
        n = _n;
        int d = 1;
        while ((1 << d) < n) d++;
        par.assign(d, std::vector<int>(n));
        adj.resize(n);
        depth.resize(n);
    }

    void ae(int x, int y) {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    void gen(int root = 0) {
        par[0][root] = root;
        dfs(root);
    }

    void dfs(int src = 0) {
        for (int i = 1; i < (int) par.size(); i++) {
            par[i][src] = par[i - 1][par[i - 1][src]];
        }
        for (int nxt: adj[src]) {
            if (nxt == par[0][src]) continue;
            depth[nxt] = depth[par[0][nxt] = src] + 1;
            dfs(nxt);
        }
    }

    int jump(int x, int d) {
        for (int i = 0; i < (int) par.size(); i++) {
            if ((d >> i) & 1) {
                x = par[i][x];
            }
        }
        return x;
    }
    
    int lca(int x, int y) {
        if (depth[x] < depth[y]) std::swap(x, y);
        x = jump(x, depth[x] - depth[y]);
        if (x == y) return x;
        for (int i = (int) par.size() - 1; i >= 0; i--) {
            int nx = par[i][x];
            int ny = par[i][y];
            if (nx != ny) x = nx, y = ny;
        }
        return par[0][x];
    }
};

template <class T> struct LazySeg {
    std::vector<T> sum, lazy;
    int sz;

    void init(int sz_) {
        sz = 1;
        while (sz < sz_) sz *= 2;
        sum.assign(2 * sz, 0);
        lazy.assign(2 * sz, 0);
    }

    void push(int ind, int L, int R) {
        sum[ind] += (R - L + 1) * lazy[ind];
        if (L != R) {
            lazy[2 * ind] += lazy[ind];
            lazy[2 * ind + 1] += lazy[ind];
        }
        lazy[ind] = 0;
    }

    void pull(int ind) {
        sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
    }

    void build() {
        for (int i = sz - 1; i >= 1; i--) {
            pull(i);
        }
    }

    void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (hi < L || R < lo) return ;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind, L, R);
            return;
        }
        int M = (L + R) / 2;
        upd(lo, hi, inc, 2 * ind, L, M);
        upd(lo, hi, inc, 2 * ind + 1, M + 1, R);
        pull(ind);
    }

    T qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return sum[ind];
        int M = (L + R) / 2;
        return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
    }
};

const bool VALUES_IN_VERTICES = false;

template <class T> class HeavyLight {
    std::vector<int> parent, heavy, depth, root, tree_pos;
    LazySeg<T> tree;

    template <class G> int dfs(const G& graph, int v) {
        int size = 1, max_subtree = 0;
        for (int u : graph[v]) if (u != parent[v]) {
            parent[u] = v;
            depth[u] = depth[v] + 1;
            int subtree = dfs(graph, u);
            if (subtree > max_subtree) heavy[v] = u, max_subtree = subtree;
            size += subtree;
        }
        return size;
    }

    template <class B> void process_path(int u, int v, B op) {
        for (; root[u] != root[v]; v = parent[root[v]]) {
            if (depth[root[u]] > depth[root[v]]) std::swap(u, v);
            op(tree_pos[root[v]], tree_pos[v]);
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        op(tree_pos[u] + (VALUES_IN_VERTICES ? 0 : 1), tree_pos[v]);
    }

public:
    template <class G>
    void init(const G& graph, vi& roots) {
        int n = (int) graph.size();
        heavy.assign(n, -1);
        parent.assign(n, 0);
        depth.assign(n, 0);
        root.assign(n, 0);
        tree_pos.assign(n, 0);
        tree.init(n);
        trav(r, roots) {
            parent[r] = -1;
            depth[r] = 0;
            dfs(graph, r);
        }
        for (int i = 0, current_pos = 0; i < n; ++i)
            if (parent[i] == -1 || heavy[parent[i]] != i)
            for (int j = i; j != -1; j = heavy[j]) {
                root[j] = i;
                tree_pos[j] = current_pos++;
            }
    }

    void modify_path(int u, int v, const T& value) {
        process_path(u, v, [this, &value](int l, int r) { tree.upd(l, r, value); });
    }
    
    T query_path(int u, int v) {
        T res = 0;
        process_path(u, v, [this, &res](int l, int r) { res += tree.qsum(l, r); });
        return res;
    }
};

struct BCC {
    int n, time, num_comps; 
    std::vector<int> ord, low, id; 
    // order encountered, earliest time in subtree, component id
    std::vector<std::vector<int>> adj, comps, tree;
    // adj, comps storage, bridge block tree
    std::vector<std::pair<int, int>> bridge;
    // bridges
    
    void init(int n_) {
        num_comps = time = 0;
        n = n_;
        ord.assign(n, -1);
        low.assign(n, 0);
        id.assign(n, -1);
        adj.assign(n, std::vector<int>());
        comps.clear();
        tree.clear();
    }

    void ae(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool is_bridge(int u, int v) {
        if (ord[u] > ord[v])
            std::swap(u, v);
        return ord[u] < low[v];
    }

    void dfs(int src, int par) {
        ord[src] = low[src] = time++;
        bool bic = false; // accounts for double edges
        for (int nxt : adj[src]) { 
            if (nxt == par && !bic) {
                bic = true;
                continue;
            }
            if (ord[nxt] != -1) {
                low[src] = std::min(low[src], ord[nxt]);
                continue;
            }
            dfs(nxt, src);
            low[src] = std::min(low[src], low[nxt]);
            if (is_bridge(src, nxt))
                bridge.emplace_back(src, nxt);
        }
    }

    void fill_component(int src) {
        comps[id[src]].push_back(src);
        for (int nxt : adj[src]) {
            if (id[nxt] != -1 || is_bridge(nxt, src))
                continue;
            id[nxt] = id[src];
            fill_component(nxt);
        }
    }

    void add_component(int src) {
        if (id[src] != -1)
            return;
        id[src] = num_comps++;
        comps.emplace_back();
        fill_component(src);
    }
    
    int build() {
        for (int i = 0; i < n; i++) 
            if (ord[i] == -1)
                dfs(i, -1);
        for (int i = 0; i < n; i++) 
            add_component(i);
        tree.resize(num_comps);
        for (auto& b : bridge) {
            int u = id[b.first];
            int v = id[b.second];
            tree[u].push_back(v);
            tree[v].push_back(u);            
        }
        return num_comps;
    }
};

int n, m, sz;

HeavyLight<int> H;
BCC B;
LCAJump L;
map<pi, int> conv;

pi cp(int u, int v) {
    if (u > v) swap(u, v);
    return {u, v};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    B.init(n);
    vi ans(m, -1); // -1 is both
    vector<array<int, 3>> ed;
    f0r(i, m) {
        int u, v; cin >> u >> v;
        u--, v--;
        B.ae(u, v);
        ed.pb({u, v, i});
    }
    B.build();
    trav(e, ed) {
        if (B.id[e[0]] != B.id[e[1]]) {
            int u = B.id[e[0]];
            int v = B.id[e[1]];
            conv[mp(u, v)] = e[2];
        }
    }

    vpi tree;
    vi vis(sz(B.tree));
    function<void(int, int)> dfs = [&](int src, int par) {
        if (par != -1) {
            tree.eb(src, par);
        }
        vis[src] = 1;
        trav(nxt, B.tree[src]) {
            if (nxt == par) continue;
            dfs(nxt, src);
        }
    };
    vi roots;
    f0r(i, sz(B.tree)) 
        if (!vis[i]) 
            dfs(i, -1), roots.pb(i);
    H.init(B.tree, roots);
    L.init(sz(B.tree));
    trav(e, tree) {
        L.ae(e.f, e.s);
    }
    trav(r, roots) L.gen(r);
    int p; cin >> p;
    f0r(i, p) {
        int x, y; cin >> x >> y;
        // all things from x to y are directed  
        x--, y--;
        int u = B.id[x];
        int v = B.id[y];
        if (u != v) {
            int lca = L.lca(u, v);
            assert(lca < sz(B.tree));
            H.modify_path(u, lca, 1);
            H.modify_path(v, lca, -1);
        }
    }
    trav(e, tree) {
        int u = e.f;
        int p = e.s;
        int val = H.query_path(u, p);
        int l = -1;
        int r = -1;
        if (val > 0) {
            l = u;
            r = p;
        } else if (val < 0) {
            l = p;
            r = u;
        }
        if (l != -1) {
            if (conv.find({l, r}) != conv.end()) {
                ans[conv[{l, r}]] = 1;
            } else {
                ans[conv[{r, l}]] = 0;
            }
        }
    }
    f0r(i, m) {
        if (ans[i] == -1) {
            cout << "B";
        } else if (ans[i] == 1) {
            cout << "R";
        } else {
            cout << "L";
        }
    }
    cout << '\n';

    return 0;
}

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