Submission #1309621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309621		damamila	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	332 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1e18

int n, m, k;
vector<vector<pair<int, int>>> g, g2;
vector<pair<int, int>> edges;
vector<int> num, low, comp;
int dfscnt = 0, compcnt = 0;
stack<int> s;
string ans;
vector<vector<int>> jump;
vector<int> dep, dp;

void tarjan(int u, int p) {
    if (num[u] != -1) return;
    // cout << u << " " << p << endl;
    num[u] = low[u] = dfscnt;
    dfscnt++;
    s.push(u);
    for (auto [v, x] : g[u]) {
        if (v == p) continue;
        if (num[v] == -1) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], num[v]);
        }
    }
    if (num[u] == low[u]) {
        int v = s.top();
        while (v != u) {
            s.pop();
            comp[v] = compcnt;
            v = s.top();
        }
        comp[v] = compcnt;
        s.pop();
        compcnt++;
    }
}

void dfs(int u, int p, int d) {
    jump[u][0] = p;
    dep[u] = d;
    for (auto [v, x] : g2[u]) {
        if (v == p) continue;
        dfs(v, u, d+1);
    }
}

void pp() {
    for (int j = 1; j < 30; j++) {
        for (int i = 0; i < compcnt; i++) {
            jump[i][j] = jump[jump[i][j-1]][j-1];
            // cout << jump[i][j] << " ";
        }
        // cout << endl;
    }
}

int lift(int a, int d) {
    for (int i = 0; i < 30; i++) {
        if ((1<<i)&d) {
            a = jump[a][i];
        }
    }
    return a;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    a = lift(a, dep[a]-dep[b]);
    for (int i = 29; i >= 0; i--) {
        if (jump[a][i] != jump[b][i]) {
            a = jump[a][i];
            b = jump[b][i];
        }
    }
    if (a != b) a = jump[a][0];
    return a;
}

int dfs2(int u, int p) {
    // cout << u << " " << p << endl;
    int cnt = 0;
    for (auto [v, x] : g2[u]) {
        if (v == p) continue;
        int tmp = dfs2(v, u);
        if (tmp) {
            // cout << "JAAA: " << v << " " << u <<  " _ " << edges[x].first << " " << edges[x].second << endl;
            if (edges[x].first == u) ans[x] = 'R';
            else ans[x] = 'L';
        }
        cnt += tmp;
    }
    cnt += dp[u];
    // cout << u << " " << p << ": " << cnt << endl;
    return cnt;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    edges = vector<pair<int, int>> (m);
    g = vector<vector<pair<int, int>>> (n);
    num = low = comp = vector<int> (n, -1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        edges[i] = {a, b};
        g[a].push_back({b, i});
        g[b].push_back({a, i});
        ans.push_back('B');
    }
    tarjan(0, 0); //Find SCCs
    /*
    for (int i = 0; i < n; i++) {
        cout << comp[i] << " ";
    }
    cout << endl;
    */
    g2 = vector<vector<pair<int, int>>> (compcnt);
    jump = vector<vector<int>> (compcnt, vector<int> (30, -1));
    dep = vector<int> (compcnt, -1);
    dp = vector<int> (compcnt, 0);
    for (int i = 0; i < n; i++) {
        for (auto [v, x] : g[i]) {
            if (comp[i] == comp[v]) continue;
            g2[comp[i]].push_back({comp[v], x});
        }
    }
    for (int i = 0; i < m; i++) {
        edges[i] = {comp[edges[i].first], comp[edges[i].second]};
    }
    dfs(0, 0, 0);
    pp();
    cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        int c = lca(comp[a], comp[b]);
        dp[comp[a]]++;
        dp[comp[b]]++;
        dp[c] -= 2;
        // cout << "C: " << c << endl;
    }
    dfs2(0, 0);
    cout << ans << endl;
}

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