Submission #161692

#	Time	Username	Problem	Language	Result	Execution time	Memory
161692		Minnakhmetov	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	239 ms	34552 KiB

oneway

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

struct E {
    int to, i;
    bool straight;
};

const int N = 1e5 + 5, L = 19;
vector<E> g[N], g2[N], t[N];
int tin[N], mnt[N], tint[N], toutt[N], w[N][2], par[N][L],
    col[N];
int timer = 1;
string ans;

bool used[N];

void dfs(int node, int anc) {
    mnt[node] = tin[node] = timer++;

    for (E e : g[node]) {
        if (e.i != anc) {
            if (!tin[e.to]) {
                dfs(e.to, e.i);
                mnt[node] = min(mnt[node], mnt[e.to]);
            }
            else {
                mnt[node] = min(mnt[node], tin[e.to]);
            }

            if (mnt[e.to] <= tin[node]) {
                g2[node].push_back(e);
                g2[e.to].push_back({node, e.i, e.straight ^ 1});
            }
        }
    }
}

void dive(int node, int c) {
    col[node] = c;

    for (E e : g2[node]) {
        if (col[e.to] == -1) {
            dive(e.to, c);
        }
    }

    for (E e : g[node]) {
        if (col[e.to] != -1 && col[e.to] != col[node]) {
            t[col[node]].push_back({col[e.to], e.i, e.straight});
            t[col[e.to]].push_back({col[node], e.i, e.straight ^ 1});
        }
    }
}

void walk(int node) {
    tint[node] = ++timer;
    for (int i = 1; i < L; i++) {
        par[node][i] = par[par[node][i - 1]][i - 1];
    }

    for (E e : t[node]) {
        if (e.to != par[node][0]) {
            par[e.to][0] = node;
            walk(e.to);
        }
    }

    toutt[node] = timer;
}

bool upper(int a, int b) {
    return tint[a] <= tint[b] && toutt[a] >= toutt[b];
}

int getLca(int a, int b) {
    if (upper(a, b))
        return a;
    for (int i = L - 1; i >= 0; i--) {
        if (!upper(par[a][i], b))
            a = par[a][i];
    }
    return par[a][0];
}

void roam(int node) {
    used[node] = 1;

    for (E e : t[node]) {
        if (e.to != par[node][0]) {
            roam(e.to);
            if (w[e.to][0]) {
                ans[e.i] = (e.straight ? 'L' : 'R');
            }
            else if (w[e.to][1]) {
                ans[e.i] = (e.straight ? 'R' : 'L');
            }
            w[node][0] += w[e.to][0];
            w[node][1] += w[e.to][1];
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m, p;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back({b, i, true});
        g[b].push_back({a, i, false});
    }

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

    fill(col, col + n, -1);
    int cc = 0;

    for (int i = 0; i < n; i++) {
        if (col[i] == -1) {
            dive(i, cc++);
        }
    }

    // for (int i = 0; i < cc; i++) {
    //     for (E e : t[i]) {
    //         cout << i + 1 << " " << e.to + 1 << "\n";
    //     }
    // }

    for (int i = 0; i < cc; i++) {
        if (!tint[i]) {
            fill(par[i], par[i] + L, i);
            walk(i);
        }
    }

    ans.resize(m, 'B');

    cin >> p;

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;

        a = col[a];
        b = col[b];

        int lca = getLca(a, b);

        w[a][0]++;
        w[lca][0]--;
        w[b][1]++;
        w[lca][1]--;
    }

    for (int i = 0; i < cc; i++) {
        if (!used[i])
            roam(i);
    }

    cout << ans;

    return 0;
}

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