Submission #1258502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258502		dex111222333444555	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	136 ms	29736 KiB

oneway

#include <bits/stdc++.h>
#define dbg(x) "[" #x " = " << x << "]"
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
const int MAXN = 1e5 + 5, LOG = 20;

template<class X, class Y>
    bool minimize(X &x, const Y &y){
        if (x > y){
            x = y; return 1;
        }
        return 0;
    }

struct edge{
    int u, v;
    edge(int _u = 0, int _v = 0): u(_u), v(_v) {};
    int other(int &x){
        return u ^ v ^ x;
    }
    bool isLeft(int x){
        return u == x;
    }
};

int numNode, numEdge, numQuery, low[MAXN], num[MAXN], mark[MAXN], down[MAXN], go[MAXN], up[MAXN][LOG], h[MAXN], res[MAXN];
bool visited[MAXN];
vector<int> adj[MAXN], nadj[MAXN], can;
stack<int> st;
edge e[MAXN];

void tarjan(int u, int par = 0){
    low[u] = num[u] = ++num[0];
    st.push(u);
    for(int id: adj[u]) if (id != par){
        int v = e[id].other(u);
        if (!num[v]){
            tarjan(v, id);
            minimize(low[u], low[v]);
            if (low[v] == num[v]) can.push_back(id);
        }else minimize(low[u], num[v]);
    }
    if (low[u] != num[u]) return;
    int v;
    do{
        v = st.top(); st.pop(); mark[v] = u;
    }while(v != u);
}

void dfsInit(int u, int par = 0){
    visited[u] = 1;
    for(int id: nadj[u]) if (id != par){
        int v = e[id].other(u);
        h[v] = h[u] + 1;
        up[v][0] = u;
        for(int i = 1; i < LOG; i++)
            up[v][i] = up[up[v][i - 1]][i - 1];
        dfsInit(v, id);
    }
}

int lca(int u, int v){
    if (h[u] < h[v]) swap(u, v);
    int k = h[u] - h[v];
    for(int i = LOG - 1; i >= 0; i--) if (BIT(k, i)) u = up[u][i];
    if (u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) if (up[u][i] != up[v][i])
        u = up[u][i], v = up[v][i];
    return up[u][0];
}

int tmp;
void dfs(int u, int par = 0){
    visited[u] = 1;
    for(int id: nadj[u]) if (id != par){
        int v = e[id].other(u);
        dfs(v, id);
        down[u] += down[v]; go[u] += go[v];
        if (go[v] > 0) res[id] = (e[id].isLeft(u) ? 2: 1);
        if (down[v] > 0) res[id] = (e[id].isLeft(u) ? 1: 2);
    }
}

void input(){
    cin >> numNode >> numEdge;
    for(int i = 1; i <= numEdge; i++){
        cin >> e[i].u >> e[i].v;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
}


void solve(){
    tarjan(1);
    int u, v;
    for(int i = 1; i <= numNode; i++) if (!num[i]) tarjan(i);
    for(int x: can){
        u = mark[e[x].u], v = mark[e[x].v];
        e[x].u = u; e[x].v = v;
        nadj[u].push_back(x);
        nadj[v].push_back(x);
    }
    for(int i = 1; i <= numNode; i++) if (!visited[i]) dfsInit(i);
    cin >> numQuery;
    while(numQuery--){
        cin >> u >> v;
        u = mark[u], v = mark[v];
        int p = lca(u, v);
        go[u]++; go[p]--;
        down[v]++; down[p]--;
    }
    memset(visited, 0, sizeof visited);
    for(int i = 1; i <= numNode; i++) if (!visited[i]) dfs(i);
//    for(int i = 1; i <= numNode; i++) cout << dp[i] << ' '; cout << '\n';
//    for(int i = 1; i <= numNode; i++) cout << res[i] << ' '; cout << '\n';
//    cout << root << ": \n";
//    for(int i = 1; i <= numEdge; i++) cout << res[i] << ' '; cout << '\n';
//    for(int i = 1; i <= numEdge; i++) cout << res[i] << ' '; cout << '\n';
    for(int i = 1; i <= numEdge; i++) cout << (res[i] == 0 ? 'B': (res[i] == 1 ? 'R': 'L'));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solve();
}

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