Submission #1312967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312967		888313666	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	121 ms	30720 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _ <<' '<<
#define print(x) cout<<#x<<": "<<(x)<<'\n'

int n,m,q,c=-1,k,d=-1;
vector<vector<array<int, 2>>> adj, aj2;
vector<array<int, 2>> eg;
vector<int> num, low, bg, cmp, up, dp, par, vis, in, out, res;
vector<vector<int>> st;

void dfs(const int u, const int p) {
    num[u]=low[u]=++c;
    bool flag=true;
    for (const auto [v, i]:adj[u]) {
        if (v==p && flag) {
            flag=false;
            continue;
        }
        if (num[v]==-1) {
            dfs(v, u);
            low[u]=min(low[u], low[v]);
            if (low[v]>num[u]) bg[i]=1;
        }
        low[u]=min(low[u], num[v]);
    }
}

void tj(){
    for (int i=0; i<n; i++) if (num[i]==-1) dfs(i, i);
}

void dfs2(const int u) {
    cmp[u]=c;
    for (const auto [v, i]:adj[u]) if (!bg[i] && cmp[v]==-1) {
        dfs2(v);
    }
}

void dfs3(const int u) {
    vis[u]=1;
    in[u]=++d;
    for (const auto [v, i]:aj2[u]) if (!vis[v]) {
        par[v]=u;
        dfs3(v);
    }
    out[u]=d;
}

bool anc(const int a, const int b) {
    return in[a]<=in[b] && out[b]<=out[a];
}

int lca(const int a, const int b) {
    if (anc(a, b)) return a;
    if (anc(b, a)) return b;
    int x=a;
    for (int i=k-1; i>=0; --i) if (!anc(st[i][x], b)) x=st[i][x];
    return st[0][x];
}

void dfs4(const int u) {
    vis[u]=1;
    for (const auto [v, i]:aj2[u]) if (v!=par[u]) {
        dfs4(v);
        if (dp[v]) {
            if (cmp[eg[i][0]]==u) res[i]=1;
            else res[i]=-1;
        } else if (up[v]) {
            if (cmp[eg[i][1]]==u) res[i]=1;
            else res[i]=-1;
        }
        dp[u]+=dp[v];
        up[u]+=up[v];

    }
    assert((!up[u]) || (!dp[u]));
}

int main(){ 
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m;
    adj.resize(n);
    eg.resize(m);
    num.assign(n, -1);
    low.assign(n, -1);
    bg.assign(m, 0);
    cmp.assign(n, -1);
    res.assign(m, 0);
    for (int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        adj[--a].push_back({--b, i});
        adj[b].push_back({a, i});
        eg[i]={a, b};
    }
    //cout<<'a'<<endl;
    tj();
    //cout<<'b'<<endl;
    c=0;
    for (int i=0; i<n; i++) if (cmp[i]==-1) {
        dfs2(i);
        ++c;
    }
    //cout<<'c'<<endl;
    aj2.resize(c);
    par.assign(c, 0);
    in.assign(c, -1);
    out.assign(c, -1);
    vis.assign(c, 0);
    for (int i=0; i<m; i++) if (bg[i]) {
        aj2[cmp[eg[i][0]]].push_back({cmp[eg[i][1]], i});
        aj2[cmp[eg[i][1]]].push_back({cmp[eg[i][0]], i});
    }
    //cout<<'d'<<endl;
    for (int i=0; i<c; i++) if (!vis[i]) {
        par[i]=i;
        dfs3(i);
    }
    up.assign(c, 0);
    dp=up;
    k=max(1, 32-__builtin_clz(c));
    //cout<<'e'<<endl;
    cin>>q;
    st.assign(k, vector<int>(c, 0));
    st[0]=par;
    for (int i=1; i<k; i++) for (int j=0; j<c; j++) {
        st[i][j]=st[i-1][st[i-1][j]];
    }
    for (int i=0; i<q; i++) {
        int a,b;
        cin>>a>>b;
        a=cmp[--a];
        b=cmp[--b];
        const auto l=lca(a, b);
        ++up[a];
        --up[l];
        --dp[l];
        ++dp[b];
    }
    vis.assign(c, 0);
    for (int i=0; i<c; i++) if (!vis[i]) dfs4(i);
    for (const auto e:res) {
        if (e==-1) cout<<'L';
        else if (!e) cout<<'B';
        else cout<<'R';
    }
    cout<<'\n';
}   

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