Submission #697424

#	Time	Username	Problem	Language	Result	Execution time	Memory
697424		Arshi	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	4948 KiB

oneway

/**********************GOD**********************/

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <iterator>
#include <map>

using namespace std;

typedef int ll;
typedef pair<ll , ll> pll;

#define len                 length()
#define MP                  make_pair
#define fs                  first
#define sc                  second
#define pb(x)               push_back(x)
#define all(x)              x.begin() , x.end()
#define kill(x)             cout << x , exit(0)

const ll MAXN = 2e5 + 5;
const ll INF = 1e9 + 8;
const ll LOG = 23;
const ll mod = 1e9 + 7;

ll n , m , q;

vector<pll> adj[MAXN] , E;
ll dp[MAXN][2] , h[MAXN] , be[MAXN] , par[MAXN][LOG] , ans[MAXN];
bool mark[MAXN];

void DFS1(ll v)
{
    for(ll i = 1 ; i < LOG ; i ++)
        par[v][i] = par[par[v][i - 1]][i - 1];

    mark[v] = 1;
    be[v] = h[v];

    for(auto[u , _] : adj[v])
    {
        if(!mark[u])
        {
            par[u][0] = v;
            h[u] = h[v] + 1;

            DFS1(u);

            be[v] = min(be[v] , be[u]);
        }
        else if(h[u] + 1 < h[v])
            be[v] = min(be[v] , h[u]);
        else if(h[u] == h[v] + 1)
            be[u] = min(be[u] , h[u] - 1);
    }
}

void DFS2(ll v , ll id = 0)
{
    mark[v] = 1;

    for(auto[u , i] : adj[v])
        if(!mark[u])
            DFS2(u , i) ,
            dp[v][0] += dp[u][0] , dp[v][1] += dp[u][1];

    ans[id] = (dp[v][0] ? 2 : 3);
    if(be[v] < h[v]) ans[id] = 1;
}

ll GetPar(ll v , ll k)
{
    for(ll i = 0 ; i < LOG ; i ++){
        if(k >> i & 1)
            v = par[v][i];
    }

    return v;
}

ll LCA(ll v , ll u)
{
    if(h[v] < h[u]) swap(v , u);

    v = GetPar(v , h[v] - h[u]);
    if(v == u) return v;

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

    return par[v][0];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    E.pb(MP(0 , 0));
    for(ll i = 1 ; i <= m ; i ++)
    {
        ll v , u;
        cin >> v >> u;

        E.pb(MP(v , u));
        if(v == u){
            ans[i] = 1;
            continue;
        }

        adj[v].pb(MP(u , i));
        adj[u].pb(MP(v , i));
    }

    for(ll i = 1 ; i <= n ; i ++)
        if(!mark[i])
            DFS1(i);

    cin >> q;
    while(q --)
    {
        ll v , u , w;
        cin >> v >> u;

        w = LCA(v , u);

        dp[v][0] ++;
        dp[u][1] ++;
        dp[w][0] --;
        dp[w][1] --;
    }

    fill(mark , mark + n + 1 , 0);
    for(ll i = 1 ; i <= n ; i ++)
        if(!mark[i])
            DFS2(i);

    for(ll i = 1 ; i <= m ; i ++)
    {
        auto[v , u] = E[i];

        if(ans[i] == 1) { cout << "B"; continue; }
        if((h[v] > h[u] && be[v] < h[v]) || (h[u] > h[v] && be[u] < h[u])) { cout << "B"; continue; }

        if(h[v] > h[u])
        {
            if(ans[i] == 2)
                cout << "R";
            else
                cout << "L";
        }
        else
        {
            if(ans[i] == 2)
                cout << "L";
            else
                cout << "R";
        }
    }

    return 0;
}

/*!
ahkh
*/

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