제출 #1309934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309934		damamila	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	197 ms	54352 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, up, down;
vector<bool> seen;

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

void dfs(int u, int p, int d) {
    // cout << u << " " << p << " " << d << endl;
    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 (a == b) return a;
    if (dep[a] < dep[b]) swap(a, b);
    a = lift(a, dep[a]-dep[b]);
    for (int i = 29; i >= 0; i--) {
        // cout << a << " " << b << endl;
        if (jump[a][i] != jump[b][i]) {
            a = jump[a][i];
            b = jump[b][i];
        }
    }
    if (a != b) a = jump[a][0];
    return a;
}

pair<int, int> dfs2(int u, int p) {
    // cout << u << " " << p << endl;
    seen[u] = 1;
    int cntup = 0, cntdown = 0;
    for (auto [v, x] : g2[u]) {
        if (v == p) continue;
        auto [upp, dnn] = dfs2(v, u);
        if (upp) {
            // cout << "UPPP: " << v << " " << u << " " << x <<  " _ " << edges[x].first << " " << edges[x].second << endl;
            if (edges[x].first == u) ans[x] = 'L';
            else ans[x] = 'R';
        } else if (dnn) {
            // cout << "DNNN: " << v << " " << u << " " << x <<  " _ " << edges[x].first << " " << edges[x].second << endl;
            if (edges[x].first == u) ans[x] = 'R';
            else ans[x] = 'L';
        }
        cntup += upp;
        cntdown += dnn;
    }
    cntup += up[u];
    cntdown += down[u];
    // cout << u << " " << p << ": " << cntup << " " << cntdown << endl;
    return {cntup, cntdown};
}

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');
        // cout << "HERE: " << i << endl;
    }
    // cout << "JA" << endl;
    for (int i = 0; i < n; i++) {
        if (num[i] == -1) tarjan(i, -1); //Find SCCs
    }
    // cout << "DONE " << compcnt << endl;
    /*
    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);
    up = down = vector<int> (compcnt, 0);
    seen = vector<bool> (compcnt, 0);
    for (int i = 0; i < n; i++) {
        // cout << "FROM: " << comp[i] << endl;
        for (auto [v, x] : g[i]) {
            if (comp[i] == comp[v]) continue;
            g2[comp[i]].push_back({comp[v], x});
            // cout << "NEW EDGE: " << v << " " << comp[v] << endl;
        }
    }
    // cout << "DONE" << endl;
    for (int i = 0; i < m; i++) {
        edges[i] = {comp[edges[i].first], comp[edges[i].second]};
    }
    // cout << "DONE" << endl;
    for (int i = 0; i < compcnt; i++) {
        if (jump[i][0] == -1) dfs(i, i, 0);
    }
    // cout << "DONE" << endl;
    pp();
    // cout << "DONE" << endl;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        // cout << comp[a] << " " << comp[b] << endl;
        int c = lca(comp[a], comp[b]);
        up[comp[a]]++;
        down[comp[b]]++;
        up[c]--;
        down[c]--;
        // cout << "C: " << comp[a] << " " << comp[b] << " " << c << endl;
    }
    for (int i = 0; i < compcnt; i++) {
        if (!seen[i]) dfs2(i, i);
    }
    cout << ans << "\n";
}

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