제출 #951921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951921		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	348 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define Go  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl "\n"
#define ll long long
// =========================================================================================
////////////////////////////////////////////////////////////////////////////////////////////
//                          Bridges Decomposition 

// comid      : number of cur components and it's the index in bcc 
// bcc        : will contain each component separately
// in[i]      : entry time for node i 
// up[i]      : min (in[w]) such that there is an edge u - w and u in the subtree of i 
// cur        : stack to keep the curren nodes which are not in a bcc yet
// edg        : same as cur but for edges
// com[i]     : the id of the bcc of the node i
// badj       : adj for the bridges-tree 
// vadj       : adj for the A-tree 


// bcc : 2-edge connected components 
// bcc[i] : will contain the nodes of componenet i 
// and connected components are seperated using bridges

// acc : 2-vertex connected components
// acc[i] : will contain the edges of component i 
// and connected components are seperated using  A points

struct BCC {

    int n, m, tick, comid, edgeid, accid;
    vector<vector<pair<int, int>>> adj, badj; // to, edge number
    vector<pair<int, int>> bridges;
    vector<vector<int>> bcc, vadj, acc;
    vector<int> up, in, cur, com, edg, acom;
    vector<bool> visedge, isbridge, Ap;

    BCC() {  }

    BCC(int n, int m) { init(n, m); }

    void init(int n, int m) {
        this->n = n; this->m = m;
        tick = comid = edgeid = accid = 0;
        bridges.clear();
        adj.assign(n + 1, { });
        bcc.assign(1, { });
        acc.assign(1, { });
        up.assign(n + 1, 0);
        Ap.assign(n + 1, 0);
        in.assign(n + 1, 0);
        acom.assign(m + 1, 0);
        com.assign(n + 1, 0);
        isbridge.assign(m + 1, 0);
        visedge.assign(m + 1, 0);
    }

    void addedge(int x, int y) {
        edgeid++;
        adj[x].push_back({ y, edgeid });
        adj[y].push_back({ x, edgeid });
    }

    void build() {
        for (int i = 1; i <= n; i++) {
            if (!in[i]) dfs(i, 0, -1);
        }
    }

    void dfs(int node, int p, int comming) {
        up[node] = in[node] = ++tick;
        cur.push_back(node);
        int childes = 0;

        for (auto& c : adj[node]) {
            int u = c.first, id = c.second;

            if (visedge[id]) continue;
            edg.push_back(id);
            visedge[id] = 1;

            if (in[u]) {
                up[node] = min(up[node], in[u]);
                continue;
            }

            childes++;
            dfs(u, node, id);

            up[node] = min(up[node], up[u]);

            if (up[u] >= in[node] || Ap[node]) {
                Ap[node] = 1;
                acc.emplace_back();
                accid++;
                while (true) {
                    int x = edg.back(); edg.pop_back();
                    acc.back().push_back(x);
                    acom[x] = accid;
                    if (x == id) break;
                }
            }
        }

        if (up[node] > in[p]) {
            if (p) {
                bridges.push_back({ node, p });
                isbridge[comming] = 1;
            }

            comid++;
            bcc.emplace_back();

            for (; !cur.empty() && in[cur.back()] >= in[node]; cur.pop_back()) {
                bcc[comid].push_back(cur.back());
                com[cur.back()] = comid;
            }
        }
        if (!p) Ap[node] = childes > 1;
    }

    void BuildBridgesTree() {
        badj.assign(n + 1, { });

        for (int i = 1; i <= n; i++) {
            for (auto& j : adj[i]) {
                if (com[i] != com[j.first]) {
                    badj[com[i]].push_back({ com[j.first], j.second });
                    badj[com[j.first]].push_back({ com[i], j.second });
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            sort(badj[i].begin(), badj[i].end());
            badj[i].erase(unique(badj[i].begin(), badj[i].end()), badj[i].end());
        }
    }

    void BuildArtiTree() {
        vadj.assign(m + n + 2, { });
        int c = m;

        for (int i = 1; i <= n; i++) {
            if (!Ap[i]) continue;
            c++;
            for (auto& j : adj[i]) {
                vadj[c].push_back(acom[j.second]);
                vadj[acom[j.second]].push_back(c);
            }
        }

        for (int i = 1; i <= c; i++) {
            sort(vadj[i].begin(), vadj[i].end());
            vadj[i].erase(unique(vadj[i].begin(), vadj[i].end()), vadj[i].end());
        }
    }
};

void Burn_The_Problem_Alive() {
    int n; cin >> n;
    int m; cin >> m;

    BCC b(n, m);
    vector<vector<int>> edges(1);
    for (int x, y, i = 1; i <= m; i++) {
        cin >> x >> y;
        b.addedge(x, y);
        edges.push_back({ x, y });
    }
    b.build();
    b.BuildBridgesTree();

    string ans(n + 1, 'B');
    vector<int> val(m + 1);
    int q; cin >> q;

    vector<int> in(n + 1), out(n + 1);
    int tick = 0;

    function<void(int, int)> fun = [&](int node, int p) {
            in[node] = ++tick;
            for (auto& u : b.badj[node]) {
                if (u.first != p) fun(u.first, node);
            }
            out[node] = ++tick;
        };

    fun(1, 0);
    while (q--) {
        int x, y; cin >> x >> y;
        val[b.com[x]]++;
        val[b.com[y]]--;
    }

    function < void(int, int, int) > dfs = [&](int node, int p, int comming) {
            for (auto& u : b.badj[node]) {
                if (u.first == p) continue;
                dfs(u.first, node, u.second);
                val[node] += val[u.first];
            }
            if (val[node] > 0) {
                if (b.com[edges[comming][0]] == p) {
                    ans[comming] = 'L';
                }
                 else ans[comming] = 'R';
            }
            else if (val[node] < 0) {
                if (b.com[edges[comming][0]] == p) {
                    ans[comming] = 'R';
                }
                else ans[comming] = 'L';
            }
        };

    dfs(1, 0, 0);
    for (int i = 1; i <= m; i++)cout << ans[i];
}

// =========================================================================================

int32_t main() {
    Go;

    int TES = 1;             //  cin >> TES;
    while (TES--)Burn_The_Problem_Alive();

    return 0;
}

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