제출 #543188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543188		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 DisjointSetUnion  {
public:
    vector<int> compSize, parent;
    int find_head (int u) {
        while (u != parent[u]) u = parent[u];
        return u;
    }
    void join (int u, int v) {
        u = find_head(u), v = find_head(v);
        if (compSize[u] > compSize[v]) swap(u, v);
        parent[u] = v, compSize[v] += compSize[u];
    }
    DisjointSetUnion (int n) {
        parent.resize(n), compSize.assign(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
};
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);
            }
        }
    }
};
string process (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];
    }
    Graph g(s.size());
    for (auto& p: edges) {
        g.add_edge(p.first.first, p.first.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.second].push_back(p.first.first);
        bf.adj[p.first.first].push_back(p.first.second);
    }
    bf.find_bridges();
    string str = "";
    for (int i = 0; i < edges.size(); i++) {
        if (!bf.myMap[{edges[i].first.first, edges[i].first.second}]) {
            //cout << "B";
            str += 'B';
        } else {
            if (myTree.depth[edges[i].first.first] > myTree.depth[edges[i].first.second]) {
                //cout << "L";
                str += 'L';
            } else {
                //cout << "R";
                str += 'R';
            }
        }
    }
    return str;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<pair<pair<int,int>,int>> edges;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        edges.push_back({{u, v}, i});
    }
    vector<pair<int,int>> queries;
    int Q;
    cin >> Q;
    while (Q--) {
        int u, v; cin >> u >> v; u--, v--;
        queries.emplace_back(u, v);
    }
    DisjointSetUnion dsu(N);
    for (auto& p: edges) {
        dsu.join(p.first.first, p.first.second);
    }
    vector<vector<pair<pair<int,int>,int>>> edges1(N);
    vector<vector<pair<int,int>>> queries1(N);
    for (auto& p: edges) {
        edges1[dsu.find_head(p.first.first)].push_back(p);
    }
    for (auto& p: queries) {
        queries1[dsu.find_head(p.first)].push_back(p);
    }
    string ansr;
    ansr.resize(M);
    for (int i = 0; i < N; i++) {
        if (i != dsu.find_head(i)) continue;
        string s = process(edges1[i], queries1[i]);
        for (int j = 0; j < edges1[i].size(); j++) {
            ansr[edges1[i][j].second] = s[j];
        }
    }
    cout << ansr;

}

컴파일 시 표준 에러 (stderr) 메시지

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

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