oj.uz

Submission #378080

# Submission time Handle Problem Language Result Execution time Memory
378080 2021-03-16T00:41:42 Z smax One-Way Streets (CEOI17_oneway) C++17
100 / 100
 180 ms 50648 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template <typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

struct BridgeTree {
    int n, eid, ti;
    vector<int> num, id, stk;
    vector<vector<int>> comp;
    vector<pair<int, int>> edges;
    vector<vector<pair<int, int>>> adj, tree;

    BridgeTree(int _n) : n(_n), eid(0), ti(0), num(n), id(n), adj(n) {}

    void addEdge(int u, int v) {
        adj[u].emplace_back(v, eid);
        adj[v].emplace_back(u, eid);
        edges.emplace_back(u, v);
        eid++;
    }

    void init() {
        for (int u=0; u<n; u++)
            if (!num[u]) {
                dfs(u, -1);
                comp.emplace_back();
                while (!stk.empty()) {
                    id[stk.back()] = (int) comp.size() - 1;
                    comp.back().push_back(stk.back());
                    stk.pop_back();
                }
            }
        tree.resize(comp.size());
        for (auto &c : comp)
            for (int u : c)
                for (auto [v, i] : adj[u])
                    if (id[u] != id[v])
                        tree[id[u]].emplace_back(id[v], i);
    }

    int dfs(int u, int p) {
        int low = num[u] = ++ti;
        stk.push_back(u);
        for (auto [v, i] : adj[u])
            if (i != p) {
                if (!num[v]) {
                    int ret = dfs(v, i);
                    low = min(low, ret);
                    if (num[u] < ret) {
                        comp.emplace_back();
                        while (comp.back().empty() || comp.back().back() != v) {
                            id[stk.back()] = (int) comp.size() - 1;
                            comp.back().push_back(stk.back());
                            stk.pop_back();
                        }
                    }
                } else {
                    low = min(low, num[v]);
                }
            }
        return low;
    }
};

template<typename T>
struct RMQ {
    vector<vector<T>> spt;

    RMQ(const vector<T> &a) : spt(1, a) {
        int n = (int) a.size();
        for (int j=1; 1<<j<=n; j++) {
            spt.emplace_back(n - (1 << j) + 1);
            for (int i=0; i+(1<<j)<=n; i++)
                spt[j][i] = min(spt[j-1][i], spt[j-1][i+(1<<(j-1))]);
        }
    }

    T query(int i, int j) {
        int k = __lg(j - i + 1);
        return min(spt[k][i], spt[k][j-(1<<k)+1]);
    }
};

struct LCA {
    int n, cid;
    vector<int> pos, depth, comp, path, ret, par;
    vector<vector<pair<int, int>>> adj;
    RMQ<int> rmq;

    LCA(int _n) : n(_n), cid(0), pos(n), depth(n), comp(n), adj(n), rmq({}) {}

    LCA(const vector<vector<pair<int, int>>> &_adj) : n((int) _adj.size()), cid(0), pos(n), depth(n), comp(n), par(n), adj(_adj), rmq({}) {}

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

    void init() {
        for (int u=0; u<n; u++)
            if (!comp[u]) {
                cid++;
                dfs(u, -1);
            }
        rmq = RMQ<int>(ret);
    }

    void dfs(int u, int p) {
        pos[u] = (int) path.size();
        comp[u] = cid;
        path.push_back(u);
        ret.push_back(pos[u]);
        for (auto [v, i] : adj[u])
            if (v != p) {
                depth[v] = depth[u] + 1;
                par[v] = i;
                dfs(v, u);
                path.push_back(u);
                ret.push_back(pos[u]);
            }
    }

    int lca(int u, int v) {
        if (pos[u] > pos[v])
            swap(u, v);
        return path[rmq.query(pos[u], pos[v])];
    }

    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }

    bool same(int u, int v) {
        return comp[u] == comp[v];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    BridgeTree bt(n);
    for (int i=0; i<m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        bt.addEdge(u, v);
    }

    bt.init();
    LCA lca(bt.tree);
    lca.init();
    int o = (int) bt.tree.size();
    vector<pair<int, int>> dir(o, {o, -1});
    int q;
    cin >> q;
    for (int i=0; i<q; i++) {
        int s, d;
        cin >> s >> d;
        s--, d--;
        s = bt.id[s], d = bt.id[d];
        if (!lca.same(s, d))
            assert(false);
        int w = lca.lca(s, d);
        if (s != w) {
            if (dir[s].second != -1 && dir[s].second != 0)
                assert(false);
            dir[s] = min(dir[s], {lca.depth[w], 0});
        }
        if (d != w) {
            if (dir[d].second != -1 && dir[d].second != 1)
                assert(false);
            dir[d] = min(dir[d], {lca.depth[w], 1});
        }
    }

    vector<bool> vis(o);

    auto dfs = [&] (auto &self, int u, int p) -> void {
        vis[u] = true;
        for (auto [v, i] : bt.tree[u])
            if (v != p) {
                self(self, v, u);
                if (dir[v].second != -1 && dir[v].first < lca.depth[u]) {
                    if (dir[u].second != -1 && dir[u].second != dir[v].second)
                        assert(false);
                    dir[u] = min(dir[u], dir[v]);
                }
            }
    };

    string ret(m, 'B');
    for (int u=0; u<o; u++) {
        if (!vis[u])
            dfs(dfs, u, -1);
        if (dir[u].second != -1) {
            if (dir[u].second == 0 ^ bt.id[bt.edges[lca.par[u]].first] == u)
                ret[lca.par[u]] = 'L';
            else
                ret[lca.par[u]] = 'R';
        }
    }
    cout << ret << "\n";

    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:210:31: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  210 |             if (dir[u].second == 0 ^ bt.id[bt.edges[lca.par[u]].first] == u)

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 45 ms 7392 KB Output is correct
12 Correct 46 ms 8800 KB Output is correct
13 Correct 62 ms 11616 KB Output is correct
14 Correct 83 ms 19808 KB Output is correct
15 Correct 94 ms 23644 KB Output is correct
16 Correct 127 ms 43864 KB Output is correct
17 Correct 122 ms 45272 KB Output is correct
18 Correct 180 ms 43772 KB Output is correct
19 Correct 116 ms 47064 KB Output is correct
20 Correct 46 ms 9056 KB Output is correct
21 Correct 44 ms 8672 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 45 ms 7392 KB Output is correct
12 Correct 46 ms 8800 KB Output is correct
13 Correct 62 ms 11616 KB Output is correct
14 Correct 83 ms 19808 KB Output is correct
15 Correct 94 ms 23644 KB Output is correct
16 Correct 127 ms 43864 KB Output is correct
17 Correct 122 ms 45272 KB Output is correct
18 Correct 180 ms 43772 KB Output is correct
19 Correct 116 ms 47064 KB Output is correct
20 Correct 46 ms 9056 KB Output is correct
21 Correct 44 ms 8672 KB Output is correct
22 Correct 153 ms 46424 KB Output is correct
23 Correct 160 ms 44632 KB Output is correct
24 Correct 180 ms 44888 KB Output is correct
25 Correct 158 ms 50648 KB Output is correct
26 Correct 154 ms 46168 KB Output is correct
27 Correct 155 ms 44632 KB Output is correct
28 Correct 42 ms 4576 KB Output is correct
29 Correct 88 ms 9440 KB Output is correct
30 Correct 67 ms 9696 KB Output is correct
31 Correct 72 ms 10208 KB Output is correct
32 Correct 96 ms 21856 KB Output is correct