Submission #952489

#	Time	Username	Problem	Language	Result	Execution time	Memory
952489		_callmelucian	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	152 ms	41680 KiB

oneway

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
int num[mn], low[mn], sz[mn], depth[mn], timeDfs;
int up[mn][21], st[mn][21], en[mn][21];
bool isBridge[mn], vis[mn];
vector<pii> adj[mn];

void dfs (int u, int preID, int d, int p) {
    num[u] = low[u] = ++timeDfs, depth[u] = d;
    vis[u] = 1, sz[u] = 1, up[u][0] = p;
    for (int i = 1; i < 17; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (pii it : adj[u]) {
        int v, id; tie(v, id) = it;
        if (id == preID) continue;
        if (!vis[v]) {
            dfs(v, id, d + 1, u);
            sz[u] += sz[v], low[u] = min(low[u], low[v]);
            if (low[v] == num[v]) isBridge[id] = 1;
        }
        else low[u] = min(low[u], num[v]);
    }
}

int goUp (int a, int k) {
    for (int i = 0; i < 17; i++)
        if (k & (1 << i)) a = up[a][i];
    return a;
}

int lca (int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = goUp(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int i = 16; i >= 0; i--)
        if (up[a][i] != up[b][i])
            a = up[a][i], b = up[b][i];
    return up[a][0];
}

int queryST (int u) {
    int l = num[u], r = num[u] + sz[u] - 1, p = 31 - __builtin_clz(r - l + 1);
    return min(st[l][p], st[r - (1 << p) + 1][p]);
}

int queryEN (int u) {
    int l = num[u], r = num[u] + sz[u] - 1, p = 31 - __builtin_clz(r - l + 1);
    return min(en[l][p], en[r - (1 << p) + 1][p]);
}

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

    int n, m; cin >> n >> m;
    vector<pii> edge(m);
    vector<char> ans(m);

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if (a != b) {
            adj[a].push_back({b, i});
            adj[b].push_back({a, i});
        }
        else ans[i] = 'B';

        edge[i] = {a, b};
    }

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

    for (int i = 1; i <= n; i++)
        st[i][0] = en[i][0] = INT_MAX;

    int p; cin >> p;
    while (p--) {
        int a, b; cin >> a >> b;
        st[num[a]][0] = min(st[num[a]][0], depth[lca(a, b)]);
        en[num[b]][0] = min(en[num[b]][0], depth[lca(a, b)]);
    }
    for (int s = 1; (1 << s) <= n; s++) {
        for (int i = 1; i + (1 << s) - 1 <= n; i++) {
            int p = s - 1;
            st[i][s] = min(st[i][p], st[i + (1 << p)][p]);
            en[i][s] = min(en[i][p], en[i + (1 << p)][p]);
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b; bool flp = 0; tie(a, b) = edge[i];
        if (a == b) continue;
        if (depth[a] > depth[b]) {
            swap(a, b);
            flp = 1;
        }
        if (!isBridge[i]) ans[i] = 'B';
        else {
            bool up = 0, down = 0;
            if (queryST(b) <= depth[a]) up = 1;
            else if (queryEN(b) <= depth[a]) down = 1;
            if (up == down) ans[i] = 'B';
            else {
                if (up) ans[i] = (flp ? 'R': 'L');
                else ans[i] = (flp ? 'L' : 'R');
            }
        }
    }

    for (int i = 0; i < m; i++) cout << ans[i];

    return 0;
}

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