oj.uz

답안 #543248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543248 2022-03-30T00:51:27 Z Olympia One-Way Streets (CEOI17_oneway) C++17
100 / 100
 1180 ms 110388 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>

using namespace std;
class BridgeFinder {
public:
    int n; // number of nodes
    vector<vector<int>> adj; // adjacency list of graph
    map<pair<int,int>,bool> isBridge;
    vector<bool> visited;
    vector<int> tin, low;
    int timer;

    void dfs(int v, int p = -1) {
        visited[v] = true;
        tin[v] = low[v] = timer++;
        for (int 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])
                    isBridge[{v, to}] = isBridge[{to, v}] = true;
            }
        }
    }

    void find_bridges() {
        timer = 0;
        visited.assign(n, false);
        tin.assign(n, -1);
        low.assign(n, -1);
        for (int i = 0; i < n; ++i) {
            if (!visited[i])
                dfs(i);
        }
        for (int i = 0; i < adj.size(); i++) {
            sort(adj[i].begin(), adj[i].end());
            for (int j = 1; j < adj[i].size(); j++) {
                if (adj[i][j] == adj[i][j - 1]) {
                    isBridge[{i, adj[i][j]}] = isBridge[{adj[i][j], i}] = false;
                }
            }
        }
    }
};
class DisjointSetUnion {
protected:
    vector<int> parent;
    vector<int> compSize;
    const int n;
    int connectedComponents;
public:
    int getConnectedComponents() const {
        return connectedComponents;
    }

public:
    DisjointSetUnion(int sz) : n(sz), connectedComponents(sz) {
        parent.resize(sz), compSize.resize(sz);
        for (int i = 0; i < n; i++) {
            parent[i] = i, compSize[i] = 1;
        }
    }

    int find_head(int x) const {
        int cur = x;
        while (cur != parent[cur]) {
            cur = parent[cur];
        }
        return cur;
    }

    void join(int x, int y) {
        x = find_head(x);
        y = find_head(y);
        if (x == y) {
            return;
        }
        if (compSize[x] > compSize[y]) {
            swap(x, y);
            //ensures that compSize[x1] <= compSize[y1]
        }
        parent[x] = y;
        compSize[y] += compSize[x];
        connectedComponents--;
    }

    bool comp(int x, int y) {
        return (find_head(x) == find_head(y));
    }
};
class Graph {
public:
    vector<vector<int>> adj;
    vector<bool> hasVisited;
    vector<vector<int>> tree_adj;
    void dfs (int curNode) {
        hasVisited[curNode] = true;
        for (int i: adj[curNode]) {
            if (!hasVisited[i]) {
                tree_adj[curNode].push_back(i);
                tree_adj[i].push_back(curNode);
                dfs (i);
            }
        }
    }
    Graph (vector<vector<int>> adj) {
        this->adj = adj;
        hasVisited.assign(adj.size(), false);
        tree_adj.resize(adj.size());
        dfs(0);
    }
};
struct segmentTree {
    vector<int64_t> vec;
    vector<int64_t> setLater;

    void push(int v, int tl, int tr) {
        if (setLater[v] == -1) {
            return;
        }
        int tm = (tl + tr)/2;
        setLater[2 * v + 1] = setLater[v];
        vec[2 * v + 1] = setLater[v] * (tr - tm);
        setLater[2 * v] = setLater[v];
        vec[2 * v] = setLater[v] * (tm - tl + 1);
        setLater[v] = -1;
    }

    const int64_t INF = 0;

    int64_t upd(int dum, int tl, int tr, int l, int r, int64_t val) {
        if (tr < l || tl > r) {
            return INF;
        }
        if (tl >= l && tr <= r) {
            setLater[dum] = val;
            return (vec[dum] = val * (tr - tl + 1));
        }
        push(dum, tl, tr);
        int mid = (tl + tr) >> 1;
        upd(2 * dum, tl, mid, l, r, val);
        upd(2 * dum + 1, mid + 1, tr, l, r, val);
        return (vec[dum] = vec[2 * dum] + vec[2 * dum + 1]);
    }

    void upd(int l, int r, int val) {
        upd(1, 0, (int) vec.size() / 2 - 1, l, r, val);
    }

    int64_t get(int dum, int tl, int tr, int &l, int &r) {
        if (tl > r || tr < l) {
            return INF;
        }
        if (tl >= l && tr <= r) {
            return vec[dum];
        }
        push(dum, tl, tr);
        int tm = (tl + tr) >> 1;
        return get(dum * 2, tl, tm, l, r) + get(dum * 2 + 1, tm + 1, tr, l, r);
    }

    int64_t get(int l, int r) {
        return get(1, 0, (int) vec.size() / 2 - 1, l, r);
    }

    void resz(int n) {
        int sz = ((1 << (int) ceil(log2(n))));
        vec.assign(sz * 2, 0);
        setLater.assign(sz * 2, -1);
    }

};
class HeavyLightDecomposition {
public:
    vector<vector<int>> adj;
    vector<int> sub;
    vector<int> id;
    vector<int> topchain;
    vector<int> depth;
    vector<int> parent;
    segmentTree st;
    vector<vector<int>> dp;
    vector<int> en;
    vector<int> ex;
    int cntr = 0;
    const int lg2 = 30;

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

    void rec(int curNode, int prevNode) {
        parent[curNode] = prevNode;
        en[curNode] = cntr++;
        if (prevNode != -1) {
            depth[curNode] = depth[prevNode] + 1;
        } else {
            depth[curNode] = 0;
        }
        sub[curNode] = 1;
        for (int i: adj[curNode]) {
            if (i != prevNode) {
                rec(i, curNode);
                sub[curNode] += sub[i];
            }
        }
        ex[curNode] = cntr++;
    }

    HeavyLightDecomposition(int n) {
        adj.resize(n);
        sub.resize(n);
        id.resize(n);
        topchain.assign(n, -1);
        parent.resize(n);
        st.resz(n + 1);
        ex.resize(n), en.resize(n);
    }

    void dfs(int curNode, int prevNode) {
        id[curNode] = cntr++;
        vector<pair<int, int>> vec;
        for (int i: adj[curNode]) {
            if (i != prevNode) {
                vec.push_back({sub[i], i});
            }
        }
        dp[curNode].resize(32);
        dp[curNode][0] = max(prevNode, 0);
        for (int i = 1; i < dp[curNode].size(); i++) {
            dp[curNode][i] = dp[dp[curNode][i - 1]][i - 1];
        }
        if (!vec.empty()) {
            sort(vec.begin(), vec.end());
            reverse(vec.begin(), vec.end());
            topchain[vec[0].second] = topchain[curNode];
            for (int i = 1; i < vec.size(); i++) {
                topchain[vec[i].second] = vec[i].second;
            }
            for (auto &p: vec) {
                dfs(p.second, curNode);
            }
        }
    }

    void f (int a, int b, int d) {
        if (a == b) {
            return;
        }
        if (topchain[a] == topchain[b]) {
            st.upd(id[b] + 1, id[a], d);
        } else if (topchain[a] != a) {
            st.upd(id[topchain[a]] + 1, id[a], d);
            f(topchain[a], b, d);
        } else {
            st.upd(id[a], id[a], d);
            f(parent[a], b, d);
        }
    }

    bool isAncestor(int u, int v) {
        return (en[u] <= en[v] && ex[u] >= ex[v]);
    }

    int leastCommonAncestor(int u, int v) {
        if (isAncestor(u, v)) {
            return u;
        }
        if (isAncestor(v, u)) {
            return v;
        }
        for (int i = lg2; i >= 0; i--) {
            if (!isAncestor(dp[u][i], v)) {
                u = dp[u][i];
            }
        }
        return dp[u][0];
    }


    void read() {
        depth.resize(adj.size());
        dp.resize(adj.size());
        rec(0, -1); //fill in all of the subtrees
        topchain[0] = 0;
        cntr = 0;
        dfs(0, -1); //fill in all of the ids and stuff
    }
};

string ans;

void proccess (vector<pair<pair<int,int>,int>> edges, vector<pair<int,int>> queries) {
    set<int> s;
    for (auto& p: edges) s.insert(p.first.first), s.insert(p.first.second);
    map<int,int> myMap; int cntr = 0;
    for (int i: s) myMap[i] = cntr++;
    for (int i = 0; i < edges.size(); i++) {
        edges[i].first.first = myMap[edges[i].first.first], edges[i].first.second = myMap[edges[i].first.second];
    }
    for (int i = 0; i < queries.size(); i++) {
        queries[i].first = myMap[queries[i].first], queries[i].second = myMap[queries[i].second];
    }
    vector<vector<int>> adj(s.size());
    for (int i = 0; i < edges.size(); i++) {
        adj[edges[i].first.first].push_back(edges[i].first.second);
        adj[edges[i].first.second].push_back(edges[i].first.first);
    }
    BridgeFinder bf; bf.n = adj.size(); bf.adj = adj; bf.find_bridges();
    Graph gr(adj);
    adj = gr.tree_adj;
    HeavyLightDecomposition hld(gr.tree_adj.size());
    hld.adj = adj; hld.read();
    for (int i = 0; i < queries.size(); i++) {
        int lca = hld.leastCommonAncestor(queries[i].first, queries[i].second);
        hld.f(queries[i].first, lca, 1);
        hld.f(queries[i].second, lca, 2);
    }
    for (int i = 1; i < adj.size(); i++) {
        if (!bf.isBridge[{i, hld.parent[i]}]) {
            hld.st.upd(hld.id[i], hld.id[i], 0);
        }
    }
    for (int i = 0; i < edges.size(); i++) {
        int nd;
        if (hld.isAncestor(edges[i].first.second, edges[i].first.first)) {
            nd = edges[i].first.first;
        } else {
            nd = edges[i].first.second;
        }
        if (hld.st.get(hld.id[nd], hld.id[nd]) == 0) {
            ans[edges[i].second] = 'B';
        } else if (hld.st.get(hld.id[nd], hld.id[nd]) == 1) {
            if (nd == edges[i].first.first) ans[edges[i].second] = 'R';
            else ans[edges[i].second] = 'L';
        } else {
            if (nd == edges[i].first.first) ans[edges[i].second] = 'L';
            else ans[edges[i].second] = 'R';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<pair<pair<int,int>,int>> edges;
    DisjointSetUnion dsu(N);
    map<pair<int,int>,int> cnt;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        cnt[{u, v}]++, cnt[{v, u}]++;
        assert(u != v);
        edges.emplace_back(make_pair(u, v), i), dsu.join(u, v);
    }
    int Q; cin >> Q; vector<pair<int,int>> queries;
    for (int i = 0; i < Q; i++) {
        int u, v; cin >> u >> v; u--, v--;
        queries.emplace_back(u, v);
    }

    vector<pair<pair<int,int>,int>> edges1[N];
    vector<pair<int,int>> queries1[N];
    for (int i = 0; i < M; i++) {
        edges1[dsu.find_head(edges[i].first.first)].push_back(edges[i]);
    }
    for (int i = 0; i < Q; i++) {
        queries1[dsu.find_head(queries[i].first)].push_back(queries[i]);
    }
    ans.assign(edges.size(), '?');
    for (int i = 0; i < N; i++) {
        if (!edges1[i].empty()) {
            proccess(edges1[i], queries1[i]);
        }
    }
    for (int i = 0; i < edges.size(); i++) {
        if (cnt[edges[i].first] >= 2) {
            ans[i] = 'B';
        }
    }
    cout << ans << '\n';
}

Compilation message

oneway.cpp: In member function 'void BridgeFinder::find_bridges()':
oneway.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i = 0; i < adj.size(); i++) {
      |                         ~~^~~~~~~~~~~~
oneway.cpp:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int j = 1; j < adj[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~
oneway.cpp: In member function 'void HeavyLightDecomposition::dfs(int, int)':
oneway.cpp:244:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |         for (int i = 1; i < dp[curNode].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:251:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |             for (int i = 1; i < vec.size(); i++) {
      |                             ~~^~~~~~~~~~~~
oneway.cpp: In function 'void proccess(std::vector<std::pair<std::pair<int, int>, int> >, std::vector<std::pair<int, int> >)':
oneway.cpp:312:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  312 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp:315:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  315 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:319:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  319 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp:328:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  328 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:333:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  333 |     for (int i = 1; i < adj.size(); i++) {
      |                     ~~^~~~~~~~~~~~
oneway.cpp:338:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  338 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:393:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  393 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 2 ms 812 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 852 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 2 ms 812 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 297 ms 34140 KB Output is correct
12 Correct 332 ms 42928 KB Output is correct
13 Correct 486 ms 58996 KB Output is correct
14 Correct 482 ms 77444 KB Output is correct
15 Correct 571 ms 81340 KB Output is correct
16 Correct 643 ms 96816 KB Output is correct
17 Correct 615 ms 100340 KB Output is correct
18 Correct 673 ms 96816 KB Output is correct
19 Correct 612 ms 102712 KB Output is correct
20 Correct 426 ms 57088 KB Output is correct
21 Correct 314 ms 56264 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 2 ms 812 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 2 ms 816 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 297 ms 34140 KB Output is correct
12 Correct 332 ms 42928 KB Output is correct
13 Correct 486 ms 58996 KB Output is correct
14 Correct 482 ms 77444 KB Output is correct
15 Correct 571 ms 81340 KB Output is correct
16 Correct 643 ms 96816 KB Output is correct
17 Correct 615 ms 100340 KB Output is correct
18 Correct 673 ms 96816 KB Output is correct
19 Correct 612 ms 102712 KB Output is correct
20 Correct 426 ms 57088 KB Output is correct
21 Correct 314 ms 56264 KB Output is correct
22 Correct 942 ms 103884 KB Output is correct
23 Correct 1123 ms 100272 KB Output is correct
24 Correct 1180 ms 100312 KB Output is correct
25 Correct 820 ms 110388 KB Output is correct
26 Correct 954 ms 102868 KB Output is correct
27 Correct 1043 ms 100496 KB Output is correct
28 Correct 140 ms 11920 KB Output is correct
29 Correct 665 ms 59844 KB Output is correct
30 Correct 593 ms 60316 KB Output is correct
31 Correct 676 ms 60896 KB Output is correct
32 Correct 571 ms 73592 KB Output is correct