Submission #1240007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240007		phanminhanh2162022	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	119 ms	43048 KiB

oneway

#include <bits/stdc++.h>
using namespace std ;

#define int long long
#define BIT(x , i) (((x) >> (i)) & 1)
#define MASK(i) (1ll << (i))
#define pb push_back
#define LOG 17
#define endl '\n'

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

template <class X , class Y>
    bool maximize(X& x , const Y& y) {
        if(x < y) {
            x = y ;
            return true ;
        }
        return false ;
    }

const int MAXN = 1e5 + 2 ;

struct AKARI_KITO {
    int node , id ; 
    bool ahihi ;
} ;

vector <int> adj[MAXN] ; vector <pair <int , int>> e ; vector <AKARI_KITO> tree[MAXN] ; vector <bool> used(MAXN , false) , isBridge(MAXN , false) ;
int numNode , numEdge , cnt = 0 , numQueries , low[MAXN] , num[MAXN] , compID[MAXN] , par[MAXN][LOG + 1] , dep[MAXN] , goDown[MAXN] , goUp[MAXN] , leftNode[MAXN] , rightNode[MAXN] ;

void loadGraph(void) {
    cin >> numNode >> numEdge ;
    for(int i = 0 ; i < numEdge ; ++i) {
        int u , v ; cin >> u >> v ;
        leftNode[i] = u ; rightNode[i] = v ;
        adj[u].pb(i) ; adj[v].pb(i) ;
        e.pb({u , v}) ;
    }
    cin >> numQueries ;
}

void getBridge(int u) {
    low[u] = num[u] = ++cnt ;
    for(int id : adj[u]) if(!used[id]) {
        used[id] = true ;
        int v = e[id].first ^ e[id].second ^ u ;
        if(num[v] == 0) {
            getBridge(v) , minimize(low[u] , low[v]) ;
            if(low[v] > num[u]) isBridge[id] = true ;
        }
        else minimize(low[u] , num[v]) ;
    }
}

int hihi = 0 ;

void compress(void) {
    queue <int> q ;
    vector <bool> vis(numNode + 1 , false) ;
    for(int i = 1 ; i <= numNode ; ++i) if(vis[i] == false) {
        ++hihi ;
        vis[i] = true ;
        q.push(i) ;
        while(!q.empty()) {
            int u = q.front() ; q.pop() ;
            compID[u] = hihi ;
            for(int id : adj[u]) {
                if(isBridge[id] == true) continue ;
                int v = e[id].first ^ e[id].second ^ u ;
                if(vis[v] == false) vis[v] = true , q.push(v) ;
            }
        }
    }
    for(int i = 0 ; i < numEdge ; ++i) if(isBridge[i] == true) {
        int u = e[i].first , v = e[i].second ;
        bool ok1 = false , ok2 = false ;
        if(leftNode[i] == u && rightNode[i] == v) ok1 = true ;
        else ok2 = true ;
        tree[ compID[u] ].pb({compID[v] , i , ok1}) ; tree[ compID[v] ].pb({compID[u] , i , ok2}) ;
    }
}

void dfs(int u) {
    for(AKARI_KITO id : tree[u]) {
        int v = id.node ;
        if(v != par[u][0]) {
            par[v][0] = u ;
            dep[v] = dep[u] + 1 ;
            dfs(v) ;
        }
    }
}

void buildLCK(void) {
    for(int j = 1 ; j <= LOG ; ++j) for(int i = 1 ; i <= numNode ; ++i) par[i][j] = par[par[i][j - 1]][j - 1] ;
}

int LCK(int u , int v) {
    if(dep[u] < dep[v]) swap(u , v) ;
    int h = dep[u] - dep[v] ;
    for(int i = 0 ; i <= LOG ; ++i) if(BIT(h , i)) 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] ;
}

vector <char> res(MAXN) ;
vector <bool> marked(MAXN , false) ;

void rieTakahashi(int u) {
    marked[u] = true ;
    for(AKARI_KITO id : tree[u]) {
        int v = id.node , edgeID = id.id ;
        bool ok = id.ahihi ;
        if(v != par[u][0]) {
            rieTakahashi(v) ;
            goUp[u] += goUp[v] ;
            goDown[u] += goDown[v] ;
            // ok == true -> u = leftNode , v = rightNode 
            // ok == false -> u = rightNode , v = leftNode 
            if(goUp[v] > 0) res[edgeID] = (ok == true ? 'L' : 'R') ;
            else if(goDown[v] > 0) res[edgeID] = (ok == true ? 'R' : 'L') ;
            else res[edgeID] = 'B' ;
        }
    }
}

void process(void) {
    for(int i = 1 ; i <= numQueries ; ++i) {
        int u , v ; cin >> u >> v ;
        int LCA = LCK(compID[u] , compID[v]) ;
        ++goUp[compID[u]] , ++goDown[compID[v]] ;
        --goUp[LCA] , --goDown[LCA] ;
    }
    for(int i = 1 ; i <= hihi ; ++i) if(marked[i] == false) rieTakahashi(i) ;
    for(int i = 0 ; i < numEdge ; ++i) {
        if(isBridge[i] == false) cout << 'B' ;
        else cout << res[i] ;
    }
}

int32_t main(void) {
    ios_base :: sync_with_stdio(false) ;
    cout.tie(nullptr) ;
    cin.tie(nullptr) ;
    loadGraph() ;
    for(int i = 1 ; i <= numNode ; ++i) if(num[i] == 0) getBridge(i) ;
    compress() ;
    for(int i = 1 ; i <= hihi ; ++i) if(dep[i] == 0) dfs(i) ;
    buildLCK() ;
    process() ;
    return 0 ;
}

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