Submission #1074851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074851		pqthangv	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	3 ms	4956 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9 + 5;
const ll oo = 1e18 + 5;

const int MAXN = 1e5 + 5;
const int LOG = 16;

//#define int ll

int n, m, TimerDFS, low[MAXN], num[MAXN], scc_quanity, scc_id[MAXN], par[MAXN][LOG + 1];
int high[MAXN], f[MAXN];
pair<int, int> edges[MAXN];
vector<pair<int, int>> adj[MAXN];
vector<int> g[MAXN];
bool del[MAXN];
stack<int> st;

void DFS_tarjan(int u, int pid) {
    ++TimerDFS;
    st.push(u);
//    cout << u << '\n';
    num[u] = low[u] = TimerDFS;
    for (int i = 0; i < int(adj[u].size()); ++i) {
        int v = adj[u][i].first, nid = adj[u][i].second;
        if (pid != nid && del[v] == false){
            if (num[v] == 0) {
                DFS_tarjan(v, nid);
                low[u] = min(low[u], low[v]);
            } else low[u] = min(low[u], num[v]);
        }
    }

    if (low[u] == num[u]) {
        int v;
        ++scc_quanity;
        do {
            v = st.top();
            del[v] = true;
            st.pop();
            scc_id[v] = scc_quanity;
        } while (v != u);
    }
}

void DFS_high(int u, int p) {
    for (int i = 0; i < int(g[u].size()); ++i) {
        int v = g[u][i];
        if (v != p) {
            high[v] = high[u] + 1;
            par[v][0] = u;
            DFS_high(v, u);
        }
    }
}

void prepare_LCA() {
    high[0] = -1;
    DFS_high(1, -1);

    for (int j = 1; j <= LOG; ++j) {
        for (int i = 1; i <= n; ++i) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}
int LCA(int u, int v) {
    if (high[u] < high[v]) return LCA(v, u);

    int k = high[u] - high[v];

    for (int i = 0; i <= LOG; ++i) {
        if ((k >> i) & 1) {
            u = par[u][i];
        }
    }

    if (u == v) return u;

    for (int i = LOG; i >= 0; --i) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

void DFS_solve(int u, int p) {
    for (int i = 0; i < int(g[u].size()); ++i) {
        int v = g[u][i];
        if (v != p) {
            DFS_solve(v, u);
            f[u] += f[v];
        }
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        edges[i] = {u, v};
    }
    for (int i = 1; i <= n; ++i)
        if (num[i] == 0) DFS_tarjan(i, -1);
//    cout << TimerDFS << '\n';
//    cout << scc_quanity << '\n';
//    for (int i = 1; i <= n; ++i) {
//        cout << scc_id[i] << ' ';
//    }
//    cout << '\n';

    for (int i = 1; i <= m; ++i) {
        int u = scc_id[edges[i].first], v = scc_id[edges[i].second];
        // vi la vo huong nen ko co canh trung
        if (u != v) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
//    for (int i = 1; i <= scc)
    prepare_LCA();
    int q; cin >> q;
    while (q--) {
        int u, v; cin >> u >> v;
        u = scc_id[u];
        v = scc_id[v];
//        int uv = LCA(u, v);
        ++f[u];
        --f[v];
//        f[uv] -= 3;
    }

    DFS_solve(1, -1);

    for (int i = 1; i <= m; ++i) {
        int u = scc_id[edges[i].first], v = scc_id[edges[i].second];
//        cout << u << ' ' << v << ' ' << high[u] << ' ' << high[v] << ' ';
        if (u == v) {
            cout << "B";
        } else {
            if (high[u] > high[v]) {
                if (f[u] == 1) cout << "R";
                else cout << "L";
            } else if (f[v] == 1) cout << "L";
            else cout << "R";
        }
//        cout << '\n';
    }
}

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

//    freopen("oneway.inp", "r", stdin);
//    freopen("oneway.out", "w", stdout);

//    int T = 1; cin >> T; while(T--)
    solve();

    return 0;
}

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