Submission #543187

#	Time	Username	Problem	Language	Result	Execution time	Memory
543187		Olympia	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	212 KiB

oneway

#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 Tree {
public:
    vector<vector<int>> adj;
    vector<vector<int>> dp;
    vector<int> pre, post, depth, sub;
    vector<int> parent;
    int cntr = 0;
    void dfs (int curNode, int prevNode) {
        pre[curNode] = cntr++;
        sub[curNode] = 1;
        if (curNode == 0) depth[curNode] = 0;
        else depth[curNode] = depth[prevNode] + 1;
        for (int i: adj[curNode]) {
            if (i != prevNode) {
                dfs(i, curNode);
                sub[curNode] += sub[i];
            }
        }
        post[curNode] = cntr++;
    }
    bool isAncestor (int u, int v) {
        return (pre[u] <= pre[v] && post[u] >= post[v]);
    }
    int lca (int u, int v) {
        if (isAncestor(u, v)) return u;
        else if (isAncestor(v, u)) return v;
        for (int i = 31; i >= 0; i--) {
            if (!isAncestor(dp[u][i], v)) {
                u = dp[u][i];
            }
        }
        return dp[u][0];
    }
    vector<pair<int,int>> directions;
    vector<pair<int,int>> vec;
    void add_query (int u, int v) {
        if (u != lca(u, v)) directions.emplace_back(u, lca(u, v));
        if (v != lca(u, v)) directions.emplace_back(lca(u, v), v);
        vec.emplace_back(sub[u], u);
    }
    Tree (int n, vector<int> parent) {
        this->parent.resize(n), adj.resize(n), sub.resize(n);
        for (int i = 0; i < parent.size(); i++) {
            if (parent[i] >= 0) {
                adj[i].push_back(parent[i]), adj[parent[i]].push_back(i);
            }
        }
        dp.resize(n), pre.resize(n), post.resize(n), depth.resize(n);
        for (int i = 0; i < n; i++) {
            dp[i].resize(32);
            dp[i][0] = max(parent[i], 0);
        }
        for (int j = 1; j < 32; j++) {
            for (int i = 0; i < n; i++) {
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
        dfs(0, -1);
    }
    int read () {
        sort(vec.begin(), vec.end());
        int root = vec[0].second;
        queue<pair<int,int>> q;
        q.push({root, 0});
        depth.assign(adj.size(), -1);
        while (!q.empty()) {
            pair<int,int> p = q.front(); q.pop();
            if (depth[p.first] != -1) {
                continue;
            }
            depth[p.first] = p.second;
            for (int i: adj[p.first]) {
                q.push({i, p.second + 1});
            }
        }
        return vec[0].second;
    }
};
class Graph {
public:
    vector<vector<int>> adj;
    vector<bool> hasVisited;
    vector<int> parent;
    void add_edge (int u, int v) {
        adj[u].push_back(v), adj[v].push_back(u);
    }
    void dfs (int curNode) {
        hasVisited[curNode] = true;
        for (int i: adj[curNode]) {
            if (!hasVisited[i]) {
                parent[i] = curNode;
                dfs(i);
            }
        }
    }
    Graph (int n) {
        adj.resize(n);
    }
    Tree read() {
        hasVisited.assign(adj.size(), false);
        parent.assign(adj.size(), -1);
        dfs(0);
        Tree myTree(adj.size(), parent);
        return myTree;
    }
};
class BridgeFinder {
public:
    int n;
    vector<vector<int>> adj;

    vector<bool> visited;
    vector<int> tin, low;
    int timer;
    map<pair<int,int>,bool> myMap;

    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]) {
                    myMap[{v, to}] = myMap[{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);
            }
        }
    }
};
void process (vector<pair<int,int>> edges, vector<pair<int,int>> queries) {
    set<int> s;
    for (auto& p: edges) {
        s.insert(p.first), s.insert(p.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 = myMap[edges[i].first];
        edges[i].second = myMap[edges[i].second];
    }
    for (int i = 0; i < queries.size(); i++) {
        queries[i].first = myMap[queries[i].first];
        queries[i].second = myMap[queries[i].second];
    }
    Graph g(s.size());
    for (auto& p: edges) {
        g.add_edge(p.first, p.second);
    }
    Tree myTree = g.read();
    for (auto& q: queries) {
        myTree.add_query(q.first, q.second);
    }
    myTree.read();
    BridgeFinder bf;
    bf.n = s.size();
    bf.adj.resize(s.size());
    for (auto& p: edges) {
        bf.adj[p.first].push_back(p.second);
        bf.adj[p.second].push_back(p.first);
    }
    bf.find_bridges();
    for (int i = 0; i < edges.size(); i++) {
        if (!bf.myMap[{edges[i].first, edges[i].second}]) {
            cout << "B";
        } else {
            if (myTree.depth[edges[i].first] > myTree.depth[edges[i].second]) {
                cout << "L";
            } else {
                cout << "R";
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<pair<int,int>> edges;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges.emplace_back(u, v);
    }
    vector<pair<int,int>> queries;
    int Q;
    cin >> Q;
    while (Q--) {
        int u, v; cin >> u >> v; u--, v--;
        queries.emplace_back(u, v);
    }
    process(edges, queries);

}

Compilation message (stderr)

oneway.cpp: In constructor 'Tree::Tree(int, std::vector<int>)':
oneway.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < parent.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void process(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
oneway.cpp:169: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]
  169 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp:173: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]
  173 |     for (int i = 0; i < queries.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:194: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]
  194 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

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