Submission #1086442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086442		Thalleous	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	133 ms	48332 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
#define maxN 1000000
typedef long long ll;
const int N = 100000;
const int M = 100000;
const int P = 100000;
const int K = 18;

ll n, m, q;
vector<pair<ll, ll>> adj[N];  // Original adjacency list
ll edge[M][2];                 // Edge information
ll path[P][3];                 // Path queries

ll bridge[M];                  // Tracks bridge edges
ll comp[N];                    // Component array
char label[M + 1];              // Labels for edges ('B', 'L', 'R')
vector<pair<ll, ll>> adjc[N];  // Compressed adjacency list

ll t = 0;
ll lo[N], ind[N];              // Tarjan's algorithm data
ll v[N];                       // Visited array for component finding
ll depth[N];                   // Depth for DFS
ll parent[N][2];               // Parent and edge index
ll p[N][K];                    // LCA sparse table
ll direction[N];               // Edge direction array
bool ok = true;                 // To check if the solution is valid

void tarjan(ll x, ll par = -1) {
    ind[x] = lo[x] = t++;
    for (auto& yi : adj[x]) {
        ll y = yi.first, i = yi.second;
        if (i == par) continue;
        if (ind[y] == -1) {
            tarjan(y, i); lo[x] = min(lo[x], lo[y]);
            if (lo[y] > ind[x]) bridge[i] = 1;  // It's a bridge
        } else lo[x] = min(lo[x], ind[y]);
    }
}

void components(ll x, ll c) {
    v[x] = 1; comp[x] = c;
    for (auto& yi : adj[x]) {
        ll y = yi.first, i = yi.second;
        if (!v[y] && !bridge[i]) components(y, c);
    }
}

void dfs(ll x, ll d = 0, ll par = -1, ll pari = -1) {
    depth[x] = d; parent[x][0] = par; parent[x][1] = pari;
    for (auto& yi : adjc[x]) {
        int y = yi.first, i = yi.second;
        if (y != par) dfs(y, d + 1, x, i);
    }
}

void LCA_init(ll c) {
    fill(&p[0][0], &p[0][0]+N*K, -1);
    for (int i = 0; i < c; i++)
        p[i][0] = parent[i][0];
    for (int k = 1; k < K; k++)
        for (int i = 0; i < c; i++)
            if (p[i][k - 1] != -1)
                p[i][k] = p[p[i][k - 1]][k - 1];
}

ll LCA_query(ll a, ll b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = K - 1; k >= 0; k--)
        if (depth[a] - (1 << k) >= depth[b])
            a = p[a][k];
    if (a == b) return a;
    for (int k = K - 1; k >= 0; k--)
        if (p[a][k] != p[b][k]) 
            a = p[a][k], b = p[b][k];
    return parent[a][0];
}

void direct(ll x, ll z, ll dir) {
    if (x == z) return;
    if (direction[x] == 0) {
        direction[x] = dir;
        ll y = parent[x][0], i = parent[x][1];
        ll a = comp[edge[i][0]], b = comp[edge[i][1]];
        if (dir == -1)
            label[i] = (a == x && b == y) ? 'R' : 'L';
        else
            label[i] = (a == y && b == x) ? 'R' : 'L';
        direct(y, z, dir);
    } else {
        if (direction[x] != dir) ok = false;
    }
}

void ReadData() {
    cin>>n>>m;
    for (int i = 0; i < m; i++) {
        ll a, b; cin>>a>>b; a--; b--;
        edge[i][0] = a; edge[i][1] = b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    fill(ind, ind + n, -1);
    for (int i = 0; i < n; i++)
        if (ind[i] == -1) tarjan(i);
    ll c = 0; fill(comp, comp + n, -1); fill(v, v + n, 0);
    for (int i = 0; i < n; i++)
        if (!v[i]) components(i, c++);
    for (int i = 0; i < m; i++) {
        if (bridge[i]) {
            ll ca = comp[edge[i][0]], cb = comp[edge[i][1]];
            adjc[ca].push_back({cb, i});
            adjc[cb].push_back({ca, i});
        }
    }
    fill(depth, depth + n, -1);
    for (int i = 0; i < n; i++)
        if (depth[i] == -1) dfs(i);
    LCA_init(c); fill(label, label + m, 'B');
    label[m] = '\0'; cin>>q;
    vector<pair<int, int>> ord;
    for (int i = 0; i < q; i++) {
        ll a, b; cin>>a>>b; a--; b--;
        path[i][0] = comp[a]; path[i][1] = comp[b];
        path[i][2] = LCA_query(comp[a], comp[b]);
        ord.push_back({depth[path[i][2]], i});
    }
    sort(ord.begin(), ord.end()); fill(direction, direction + n, 0);
    for (auto& di : ord) {
        ll i = di.second, a = path[i][0];
        ll b = path[i][1], l = path[i][2];
        direct(a, l, -1); direct(b, l, 1);
    }
    cout<<label<<endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ReadData(); return 0;
}

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