제출 #1165223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165223		MPG	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	170 ms	327680 KiB

oneway

//#pragma GCC optomize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define     max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 1e5 + 123;
ll const inf = 3e18;
ll const loG = 18; // 23
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}


ll n, m, q, ans[maxn], zir[maxn], h[maxn], col[maxn], now, par[loG][maxn], mos[maxn], man[maxn];
bool borsh[maxn], mark[maxn];
vector <pair <ll, ll>> g[maxn];
vector <pair <pair <ll, ll>, ll>> yal;


void dfs(ll v, ll p, ll id){
    mark[v] = 1;
    h[v] = h[p] + 1;
    zir[v] = h[v];
    for (auto u : g[v]){
        if (!mark[u.first]){
            dfs(u.first, v, u.second);
            zir[v] = min(zir[v], zir[u.first]);
        }
        else if (u.first != p){
            zir[v] = min(zir[v], h[u.first]);
        }
    }
    if (id){
        if (zir[v] == h[v])
            borsh[id] = 1;
    }
}


void sfd(ll v){
    mark[v] = 1;
    col[v] = now;
    for (auto u : g[v]){
        if (!mark[u.first])
            sfd(u.first);
    }
}   


void dfs2(ll v, ll p){
    mark[v] = 1;
    h[v] = h[p] + 1;
    par[0][v] = p;
    man[v] = h[v];
    mos[v] = h[v];
    for (auto u : g[v]){
        if (u.first != p){
            dfs2(u.first, v);
        }
    }
}


ll jump(ll v, ll d){
    for (int i = 0; i<  loG; i++)
        if(d & (1 << i))
            v = par[i][v];
    return v;
}
ll lca(ll u, ll v){
    if (h[u] < h[v])
        swap(u, v);
    u = jump(u, h[u] - h[v]);
    if(u == v) return u;
    for(int i = loG - 1; i >= 0; i--)
        if(par[i][u] != par[i][v])
            u = par[i][u],
            v = par[i][v];
    return par[0][u];
}

void dfs3(ll v, ll p, ll id){
    mark[v] = 1;
    //cout << "i am fucking " << v << ' ' << p << ' ' << h[v] << ' ' << man[v] << ' ' << mos[v] << endl;
    for (auto u : g[v]){
        if (u.first != p){
            dfs3(u.first, v, u.second);
            man[v] = min(man[v], man[u.first]);
            mos[v] = min(mos[v], mos[u.first]);
        }
    }
    if (id){
        ll a = yal[id - 1].first.first, b = yal[id - 1].first.second;
        a = col[a], b = col[b];
        //cout << "man hastam " << v << ' ' << p << ' ' << id << ' ' << a << ' ' << b << ' ' << man[v] << ' ' << mos[v] << endl;
        if (man[v] != h[v]){
            if (a == p)
                ans[id] = 1;
            else
                ans[id] = 2;            
        }
        else if (mos[v] != h[v]){
            if (a == p)
                ans[id] = 2;
            else
                ans[id] = 1;
        }
    }
}



void Solve(){

cin >> n >> m;
for (int i = 1; i < m + 1; i++){
    ll a, b; cin >> a >> b;
    yal.pb({{a, b}, i});
    g[a].pb({b, i});
    g[b].pb({a, i});
}
for (int i = 1; i < n + 1; i++){
    if (!mark[i])
        dfs(i, i, 0);
}

// for (int i = 1; i < m + 1; i++)
//     cout << i << ' ' << borsh[i] << endl;

for (int i = 1; i < n + 1; i++){
    g[i].clear();
    mark[i] = 0;
}
for (auto p : yal){
    if (!borsh[p.second]){
        ll a = p.first.first, b = p.first.second;
        g[a].pb({b, p.second});
        g[b].pb({a, p.second});
    }
}
for (int i = 1; i < n + 1; i++){
    if (!mark[i]){
        now++;
        sfd(i);
    }
}

// for (int i = 1; i < n + 1; i++)
//     cout << i << ' ' << col[i] << endl;


for (int i = 1; i < n + 1; i++){
    g[i].clear();
    mark[i] = 0;
    h[i] = 0;
    man[i] = inf;
    mos[i] = inf;
}
for (auto p : yal){
    if (borsh[p.second]){
        ll a = p.first.first, b = p.first.second;
        a = col[a], b = col[b];
        g[a].pb({b, p.second});
        g[b].pb({a, p.second});
    }
}
for (int i = 1; i < n + 1; i++){
    if (!mark[i])
        dfs2(i, i);
}

//cout << "akh " << man[8] << ' ' << mos[8] << endl;



for (int i = 1; i < n + 1; i++)
    mark[i] = 0;
for (int i = 1; i < loG; i++)
    for (int j = 1; j < n + 1; j++)
        par[i][j] = par[i - 1][par[i - 1][j]];




cin >> q;
while (q--){
    ll a, b; cin >> a >> b;
    a = col[a], b = col[b];
    if (a == b)
        continue;
    ll c = lca(a, b);
    //cout << a << ' ' << b << ' ' << c << endl; 
    //cout << "vayy " << man[8] << ' ' << mos[8] << endl;
    man[b] = min(man[b], h[c]);
    mos[a] = min(mos[a], h[c]);
}
for (int i = 1; i < n + 1; i++){
    if (!mark[i])
        dfs3(i, i, 0);
}


for (int i = 1; i < m + 1; i++){
    if (ans[i] == 1)
        cout << 'R';
    else if (ans[i] == 2)
        cout << 'L';
    else
        cout << 'B';
}
cout << endl;

}





int main(){
sariE;// filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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