Submission #866800

#	Time	Username	Problem	Language	Result	Execution time	Memory
866800		Eliorita	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	2 ms	11612 KiB

oneway

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define int long long
#define getbit(u,i) ((u>>i)&1)
#define N 100001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int n,m,q,num[N],low[N],F[N],Dp[N],l[N],r[N],cnt,Count,h[N],p[N][18],mask[N];
stack<int> st;
vector<int> g[N];
vector<ii> vec[N];
string ans;
void visit(int u,int pre)
{
    low[u]=num[u]=++cnt;
    st.push(u);
    int cur=0;
    for(int v : g[u])
    {
        if(pre!=v||cur==1)
        {
            if(num[v]) low[u]=min(low[u],num[v]);
            else
            {
                visit(v,u);
                low[u]=min(low[u],low[v]);
            }
        }
        else cur++;
    }
    if(num[u]==low[u])
    {
        int v;
        Count++;
        do
        {
            v=st.top();
            mask[v]=Count;
            st.pop();
        } while(v!=u);
    }
}
void dfs(int u,int pre)
{
    num[u]=1;
    h[u]=h[pre]+1;
    for(ii v : vec[u])
    {
        if(v.x==pre) continue;
        dfs(v.x,u);
    }
}
void calc(int u,int pre)
{
    for(ii v : vec[u])
    {
        if(v.x==pre) continue;
        calc(v.x,u);
        Dp[v.y]=F[v.x];
        F[u]+=F[v.x];
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].pb(v); l[i]=u;
        g[v].pb(u); r[i]=v;
    }
    for(int i=1;i<=n;i++)
    {
        if(!num[i]) visit(i,i);
    }
    for(int i=1;i<=m;i++)
    {
        int lhs=mask[l[i]],rhs=mask[r[i]];
        if(lhs!=rhs)
        {
            vec[lhs].pb({rhs,i});
            vec[rhs].pb({lhs,i});
        }
    }
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)
    {
        if(!num[i]) dfs(i,i);
    }
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        u=mask[u]; v=mask[v];
        F[u]++;
        F[v]--;
    }
    calc(1,0);
    for(int i=1;i<=m;i++)
    {
        if(Dp[i]==0) ans+='B';
        else
        {
            if(h[mask[l[i]]]<h[mask[r[i]]])
            {
                if(Dp[i]<0) ans+='R';
                else ans+='L';
            }
            else
            {
                if(Dp[i]<0) ans+='L';
                else ans+='R';
            }
        }
    }
    cout<<ans;
}

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