Submission #503447

#	Time	Username	Problem	Language	Result	Execution time	Memory
503447		Lobo	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	86 ms	19564 KiB

oneway

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

int n, m, q;
int mark[maxn], span[maxn], h[maxn];
int low[maxn], ps[maxn];
vector<pair<int,int>> g[maxn];
pair<int,int> edg[maxn];
vector<int> roots;

void dfstree(int u, int idant, int ant) {
    mark[u] = 1;

    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(idant == id) continue;

        if(!mark[v]) {
            span[id] = 1;
            h[v] = h[u]+1;
            dfstree(v,id,u);
        }
    }
}

void dfslow(int u, int idant, int ant) {

    low[u] = inf;
    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(id == idant) continue;

        if(span[id]) {
            dfslow(v,id,u);
            low[u] = min(low[u],low[v]);
        }
        else {
            if(h[v] < h[u]) low[u] = min(low[u],h[v]);
        }

    }
}

void dfsps(int u, int ant) {

    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(v == ant || !span[id]) continue;

        dfsps(v,u);
        ps[u]+= ps[v];
    }
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(mp(v,i));
        g[v].pb(mp(u,i));
        edg[i] = mp(u,v);
    }

    for(int i = 1; i <= n; i++) {
        if(!mark[i]) {
            dfstree(i,0,i);
            roots.pb(i);
        }
    }

    for(auto x : roots) {
        dfslow(x,0,x);
    }

    cin >> q;
    for(int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;

        ps[u]++;
        ps[v]--;
    }

    for(auto x : roots) {
        dfsps(x,x);
    }

    for(int i = 1; i <= m; i++) {
        if(edg[i].fr == edg[i].sc) {
            cout << 'B';
            continue;
        }
        int ans = 1;

        int u = edg[i].fr;
        int v = edg[i].sc;

        if(h[u] > h[v]) {swap(u,v); ans*= -1;}

        //u e pai de v

        ans*= ps[v];
        if(low[v] <= h[u] || !span[i]) {
            cout << 'B';
        }
        else {
            if(ans > 0) cout << 'L';
            else if(ans < 0) cout << 'R';
            else cout << 'B';
        }
    }

    cout << endl;


}

//encontrar todas as bridge edges com dfs tree
//caminho u->lc->v -- prefix sum ps[u]++, ps[v]-- -> dsfps
// + = subindo, - = descendo

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
    return 0;

}

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