Submission #1149907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149907		dosts	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	79 ms	46916 KiB

oneway

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 3e5+1,MOD = 1e9+7,BL = 1000;


vector<pii> edges[N];
vi bridge(N,0),tree(N),tin(N,0),low(N,0),comp(N,0),dp(N,0),realedg[N],tout(N);

int timer = 1;
void dfs(int node,int id) {
    tin[node] = low[node] = timer++;
    for (auto it : edges[node]) {
        if (it.ss == id) continue;
        if (!tin[it.ff]) {
            dfs(it.ff,it.ss);
            if (low[it.ff] >= tin[it.ff]) bridge[it.ss] = 1;
        }
        low[node] = min(low[node],low[it.ff]);
    }
}

void dfs2(int node,int compid) {
    if (comp[node]) return;
    comp[node] = compid;
    for (auto it : edges[node]) {
        if (!bridge[it.ss]) dfs2(it.ff,compid);
    }
}

void dfs3(int node,int p) {
    tin[node] = timer++;
    for (auto it : realedg[node]) {
        if (it == p) continue;
        dfs3(it,node);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void dfs4(int node,int p) {
    low[node] = 1;
    for (auto it : realedg[node]) {
        if (it == p) continue;
        dfs4(it,node);
        dp[node]+=dp[it];
    }
}

void solve() { 
    int n,m;
    cin >> n >> m;
    vector<pii> edg(m+1);
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        edg[i] = {a,b};
        edges[a].push_back({b,i});
        edges[b].push_back({a,i});
    } 
    for (int i=1;i<=n;i++) {
        if (tin[i]) continue;
        dfs(i,-1);
    }
    int ctr = 0;
    for (int i=1;i<=n;i++) {
        if (comp[i]) continue;
        dfs2(i,++ctr);
    }
    for (int i=1;i<=m;i++) {
        if (!bridge[i]) continue;
        assert(comp[edg[i].ff] != comp[edg[i].ss]);
        realedg[comp[edg[i].ff]].push_back(comp[edg[i].ss]);
        realedg[comp[edg[i].ss]].push_back(comp[edg[i].ff]);
    }
    timer = 1;
    tin.assign(n+1,0);
    for (int i=1;i<=n;i++) {
        if (!tin[i]) dfs3(i,i);
    }
    int q;
    cin >> q;
    while (q--) {
        int a,b;
        cin >> a >> b;
        int x = comp[a],y = comp[b];
        dp[x]++;
        dp[y]--;
    }
    low.assign(n+1,0);
    for (int i=1;i<=n;i++) {
        if (!low[i]) dfs4(i,i);
    }
    for (int i=1;i<=m;i++) {
        if (comp[edg[i].ff] == comp[edg[i].ss]) {
            cout << 'B';
            continue;
        }
        int swp = 0;
        int x = comp[edg[i].ff],y = comp[edg[i].ss];
        //cout << x sp y << '\n';
        if (anc(x,y)) swap(x,y),swp = 1;
        if (dp[x] == 0) {
            cout << 'B';
            continue;
        }
        char up = 'R';
        char down = 'L';
        if (swp) swap(up,down);
        cout << ((dp[x] >= 1) ? up : down);
    }
    cout << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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