Submission #348575

#	Time	Username	Problem	Language	Result	Execution time	Memory
348575		Nima_Naderi	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	156 ms	26204 KiB

oneway

///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e5 + 10;
const ll INF = 1e18;
ll n, m, q;
ll Par[MXN], Sz[MXN], Min[MXN], dis[MXN], num[MXN];
vector<pair<ll, ll>> adj[MXN], G[MXN], Edge;
bool vis[MXN], mark[MXN];
string ANS;
ll Find(ll x){
    return (Par[x] == x ? x : Par[x] = Find(Par[x]));
}
void Union(ll x, ll y){
    x = Find(x), y = Find(y);
    if(x == y) return;
    if(Sz[x] < Sz[y]) swap(x, y);
    Sz[x] += Sz[y], Par[y] = x;
}
void dfs(ll u, ll pid){
    vis[u] = 1, Min[u] = INF;
    for(auto Pr : adj[u]){
        ll v, id; tie(v, id) = Pr;
        if(id == pid) continue;
        if(vis[v]){
            Min[u] = min(Min[u], dis[v]);
            ANS[id] = 'B';
            continue;
        }
        dis[v] = dis[u] + 1;
        dfs(v, id);
        Min[u] = min(Min[u], Min[v]);
        if(Min[v] <= dis[u]) Union(u, v), ANS[id] = 'B';
    }
}
void DFS(ll u, ll par){
    mark[u] = 1;
    for(auto Pr : G[u]){
        ll v, id; tie(v, id) = Pr;
        if(v == par) continue;
        DFS(v, u);
        num[u] += num[v];
        if(num[v] == 0) ANS[id] = 'B';
        else{
            ll from = (num[v] > 0 ? v : u);
            ANS[id] = (from == Find(Edge[id - 1].first) ? 'R' : 'L');
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ANS = "$";
    for(int i = 1; i <= n; i ++) Par[i] = i, Sz[i] = 1;
    for(int i = 1; i <= m; i ++){
        ll u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        Edge.push_back({u, v});
        ANS += "N";
    }
    for(int i = 1; i <= n; i ++){
        if(!vis[i]) dfs(i, 0);
    }
    for(int i = 0; i < m; i ++){
        ll u, v; tie(u, v) = Edge[i];
        u = Find(u), v = Find(v);
        if(u == v){
            assert(ANS[i + 1] == 'B');
            continue;
        }
        assert(ANS[i + 1] == 'N');
        G[u].push_back({v, i + 1});
        G[v].push_back({u, i + 1});
    }
    cin >> q;
    while(q --){
        ll u, v; cin >> u >> v;
        u = Find(u), v = Find(v);
        num[u] ++, num[v] --;
    }
    for(int i = 1; i <= n; i ++){
        if(Par[i] != i) continue;
        if(!mark[i]) DFS(i, 0);
    }
    for(int i = 1; i <= m; i ++) assert(ANS[i] != 'N');
    cout << ANS.substr(1, m) << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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