Submission #866799

#	Time	Username	Problem	Language	Result	Execution time	Memory
866799		Eliorita	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3 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;
    p[u][0]=pre;
    for(int i=1;i<=17;i++)
    {
        p[u][i]=p[p[u][i-1]][i-1];
    }
    for(ii v : vec[u])
    {
        if(v.x==pre) continue;
        dfs(v.x,u);
    }
}
int lca(int u,int v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int i=17;i>=0;i--)
    {
        if(h[p[u][i]]>=h[v]) u=p[u][i];
    }
    if(u==v) return u;
    for(int i=17;i>=0;i--)
    {
        if(p[u][i]!=p[v][i])
        {
            u=p[u][i];
            v=p[v][i];
        }
    }
    return p[u][0];
}
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()
{
    if(fopen("demo.inp","r"))
    {
        freopen("demo.inp","r",stdin);
        freopen("demo.out","w",stdout);
    }
    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];
        int anc=lca(u,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;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:132:13: warning: unused variable 'anc' [-Wunused-variable]
  132 |         int anc=lca(u,v);
      |             ^~~
oneway.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("demo.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen("demo.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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