Submission #1173720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173720		buzdi	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	95 ms	41408 KiB

oneway

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#define ll long long

using namespace std;

const int NMAX = 1e5;
const int LOGMAX = 18;

struct Edge {
    int to, type, id;
};

int n, m, q, t, components;
pair<int, int> edges[NMAX + 1];
vector<Edge> g[NMAX + 1], tree[NMAX + 1];
vector<pair<int, int>> updates[NMAX + 1];
int dfs_time[NMAX + 1];
int low[NMAX + 1];
bool bridge[NMAX + 1];
int component[NMAX + 1];
Edge parent[NMAX + 1];
int depth[NMAX + 1];
int euler[2 * NMAX + 1], ind_e;
int LOG[2 * NMAX + 1];
int pos_euler[NMAX + 1];
int rmq[LOGMAX + 1][2 * NMAX + 1];
int answer[NMAX + 1];
pair<int, int> node_with_depth[NMAX + 1];

void DFS1(int node, int dad = 0) {
    dfs_time[node] = low[node] = ++t;
    for(auto [next_node, type, id] : g[node]) {
        if(!dfs_time[next_node]) {
            DFS1(next_node, node);
            low[node] = min(low[node], low[next_node]);
            if(low[next_node] > dfs_time[node]) {
                bridge[id] = 1;
            }
        }
        else if(next_node != dad) {
            low[node] = min(low[node], dfs_time[next_node]);
        }
    }
}

void DFS2(int node) {
    component[node] = components;
    for(auto [next_node, type, id] : g[node]) {
        if(!component[next_node] && !bridge[id]) {
            DFS2(next_node);
        }
    }
}

void DFS3(int node, Edge dad_edge = {0, 0, 0}) {
    parent[node] = dad_edge;
    depth[node] = depth[dad_edge.to] + 1;

    euler[++ind_e] = node;
    pos_euler[node] = ind_e;

    for(auto [next_node, type, id] : tree[node]) {
        if(next_node != dad_edge.to) {
            DFS3(next_node, {node, type, id});
            euler[++ind_e] = node;
        }
    }
}

void Precompute() {
    for(int i = 2; i <= ind_e; i++) {
        LOG[i] = LOG[i >> 1] + 1;
    }

    for(int i = 1; i <= ind_e; i++) {
        rmq[0][i] = euler[i];
    }
    for(int k = 1; (1 << k) <= ind_e; k++) {
        for(int i = 1; i + (1 << k) - 1 <= ind_e; i++) {
            int first_node = rmq[k - 1][i];
            int second_node = rmq[k - 1][i + (1 << (k - 1))];
            rmq[k][i] = (depth[first_node] < depth[second_node] ? first_node : second_node);
        }
    }
}

int GetLCA(int x, int y) {
    x = pos_euler[x];
    y = pos_euler[y];
    if(x > y) {
        swap(x, y);
    }

    int k = LOG[y - x + 1];
    int first_node = rmq[k][x];
    int second_node = rmq[k][y - (1 << k) + 1];
    return (depth[first_node] < depth[second_node] ? first_node : second_node);
}

void UpdatePath(int x, int y, int type_need) {
    while(x != y && !answer[parent[x].id]) {
        assert(x > 0);

        Edge curent_edge = parent[x];
        answer[curent_edge.id] = 1 + (type_need ^ curent_edge.type);
        x = curent_edge.to;
    }
}

void Update(int lca, int x, int y) {
    UpdatePath(x, lca, 1);
    UpdatePath(y, lca, 0);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        edges[i] = {a, b};
        g[a].push_back({b, 0, i});
        g[b].push_back({a, 1, i});
    }

    for(int i = 1; i <= n; i++) {
        if(!dfs_time[i]) {
            DFS1(i);
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!component[i]) {
            components++;
            DFS2(i);
        }
    }

    for(int i = 1; i <= n; i++) {
        for(auto [j, type, id] : g[i]) {
            if(component[i] != component[j]) {
                tree[component[i]].push_back({component[j], type, id});
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        if(!depth[i]) {
            DFS3(i);
        }
    }
    Precompute();

    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        x = component[x];
        y = component[y];
        updates[GetLCA(x, y)].push_back({x, y});
    }

    for(int i = 1; i <= n; i++) {
        node_with_depth[i] = {depth[i], i};
    }
    sort(node_with_depth + 1, node_with_depth + n + 1);

    for(int i = 1; i <= n; i++) {
        int node = node_with_depth[i].second;
        for(auto [x, y] : updates[node]) {
            Update(node, x, y);
        }
    }

    for(int i = 1; i <= m; i++) {
        if(answer[i] == 0) {
            cout << "B";
        }
        else if(answer[i] == 1) {
            cout << "R";
        }
        else {
            cout << "L";
        }
    }

    return 0;
}

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