Submission #467287

#	Time	Username	Problem	Language	Result	Execution time	Memory
467287		idk321	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	5404 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
vector<array<int, 2>> adj[N];
vector<array<int, 2>> adj2[N];
bool isBridge[N];
int up[N];
int in[N];
int out[N];
int timer;
int n, m;
int group[N];
array<int, 2> par[N];
int goNext[N];
array<int, 2> direction[N];
map<array<int, 2>, int> groupEdgeToNode;

void bridges(int node, array<int, 2> par) {
    in[node] = timer++;
    up[node] = in[node];

    for (auto next : adj[node]) {
        if (next[0] == par[0]) continue;
        if (in[next[0]]) {
            up[node] = min(up[node], in[next[0]]);
        } else {
            bridges(next[0], {node, next[1]});
            up[node] = min(up[node], up[next[0]]);
        }
    }

    if (node != 1 && up[node] == in[node]) {
        isBridge[par[1]] = true;
    }
}

void clean() {
    for (int i = 0; i <= n; i++) {
        up[i] = 0;
        in[i] = 0;
    }
    for (int i = 0; i <= m; i++) {
        isBridge[i] = false;
    }
    timer = 1;
}

void assignGroup(int node, int cgroup) {
    group[node] = cgroup;
    for (auto next : adj[node]) {
        if (!group[next[0]] && !isBridge[next[1]]) {
            assignGroup(next[0], cgroup);
        }
    }
}


void dfs(int node, array<int, 2> p) {

    in[node] = ++timer;
    par[node] = p;
    for (auto next : adj2[node]) {
        if (next == p) continue;
        dfs(next[0], {node, next[1]});
    }

    out[node] = timer;
}

void query(int node, int other, bool first) {
    if (goNext[node] != node) {
        query(goNext[node], other, first);
        goNext[node] = goNext[goNext[node]];
    } else {
        if (in[node] <= in[other] && out[other] <= out[node]) {

        } else {
            if (first) {
                direction[par[node][1]] = {groupEdgeToNode[{node, par[node][0]}], groupEdgeToNode[{par[node][0], node}]};

            } else {
                direction[par[node][1]] = {groupEdgeToNode[{par[node][0], node}], groupEdgeToNode[{node, par[node][0]}]};
            }
            query(goNext[par[node][0]], other, first);
            goNext[node] = goNext[par[node][0]];
        }
    }
}

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

    cin >> n >> m;
    vector<array<int, 2>> edgeNodes(m);
    for (int i = 0;  i< m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edgeNodes[i] = {a, b};
    }

    timer = 1;
    bridges(1, {-1, -1});
    string res(m, 'B');
    int cgroup = 1;
    for (int i = 1; i <= n; i++) {
        if(!group[i]) assignGroup(i, cgroup++);
    }


    for (int i = 1; i <= n; i++) {
        for (auto next : adj[i]) {
            if (group[i] != group[next[0]]) {
                groupEdgeToNode[{group[i], group[next[0]]}] = i;
                adj2[group[i]].push_back({group[next[0]], next[1]});
            }
        }
    }
    clean();
    dfs(1, {-1, -1});

    for (int i = 0; i <N; i++) goNext[i] = i;

    int p;
    cin >> p;
    for (int p1 = 0; p1 < p; p1++) {
        int x, y;
        cin >> x >> y;
        if (group[x] != group[y]) {
            query(group[x], group[y], true);
            query(group[y], group[x], false);
        }
    }

    for (int i = 0; i < m; i++) {
        array<int, 2> compareArray = {0, 0};
        if (direction[i] != compareArray) {
            if (direction[i] == edgeNodes[i]) res[i] = 'R';
            else res[i] = 'L';
        }
    }
    cout << res << "\n";
}

/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

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