Submission #46973

#	Time	Username	Problem	Language	Result	Execution time	Memory
46973		dqhungdl	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	5 ms	5112 KiB

oneway

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

typedef pair<int,int> ii;
int T,n,m,cnt=0,Time=0,Num[100005],Low[100005],In[100005],Out[100005],Pre[100005],h[100005],P[100005][20];
int add1[100005],add2[100005],sub1[100005],sub2[100005];
bool FEdge[100005],Pass1[100005],Pass2[100005];
vector<ii> Edge,gg[100005];
vector<int> g[100005];

void FindBridge(int u,int preid)
{
    Num[u]=Low[u]=++cnt;
    for(int i=0;i<gg[u].size();i++)
    {
        int v=gg[u][i].first;
        int id=gg[u][i].second;
        if(Num[v]==0)
        {
            FindBridge(v,id);
            Low[u]=min(Low[u],Low[v]);
            if(Low[v]>=Num[v])
                FEdge[id]=true;
        }
        else
        if(id!=preid)
            Low[u]=min(Low[u],Num[v]);
    }
}

void DFSComponent(int u,int kk)
{
    Pre[u]=kk;
    for(int i=0;i<gg[u].size();i++)
    {
        int v=gg[u][i].first;
        int id=gg[u][i].second;
        if(FEdge[id]==false&&Pre[v]==0)
            DFSComponent(v,kk);
    }
}

void DFSHigh(int u,int high)
{
    h[u]=high;
    In[u]=++Time;
    for(int i=0;i<g[u].size();i++)
        if(h[g[u][i]]==0)
        {
            P[g[u][i]][0]=u;
            DFSHigh(g[u][i],high+1);
        }
    Out[u]=Time;
}

int LCA(int u,int v)
{
    for(int k=17;k>=0;k--)
        if(h[P[u][k]]>=h[v])
            u=P[u][k];
        else
        if(h[P[v][k]]>=h[u])
            v=P[v][k];
    for(int k=17;k>=0;k--)
        if(P[u][k]!=P[v][k])
        {
            u=P[u][k];
            v=P[v][k];
        }
    while(u!=v)
    {
        u=P[u][0];
        v=P[v][0];
    }
    return u;
}

int Search(int u,int v)
{
    int l=0,r=g[u].size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(In[g[u][mid]]<=In[v]&&Out[v]<=Out[g[u][mid]])
            return g[u][mid];
        if(In[v]<In[g[u][mid]])
            r=mid-1;
        else
            l=mid+1;
    }
}

void SumDFS(int u,int root,int s1,int s2)
{
    Pass1[u]=(s1>0);
    Pass2[u]=(s2>0);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=root)
            SumDFS(g[u][i],u,s1-sub1[u]+add1[g[u][i]],s2-sub2[u]+add2[g[u][i]]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>m;
    int u,v,Count=0;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        Edge.push_back(ii(u,v));
        gg[u].push_back(ii(v,i));
        gg[v].push_back(ii(u,i));
    }
    for(int i=1;i<=n;i++)
        if(Num[i]==0)
            FindBridge(i,0);
    for(int i=1;i<=n;i++)
        if(Pre[i]==0)
            DFSComponent(i,++Count);
    for(int i=0;i<Edge.size();i++)
    {
        int u=Pre[Edge[i].first];
        int v=Pre[Edge[i].second];
        if(u!=v)
        {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    for(int i=1;i<=n;i++)
        if(h[i]==0)
            DFSHigh(i,1);
    for(int k=1;k<=17;k++)
        for(int i=1;i<=Count;i++)
            P[i][k]=P[P[i][k-1]][k-1];
    cin>>T;
    while(T--)
    {
        cin>>u>>v;
        u=Pre[u];
        v=Pre[v];
        int w=LCA(u,v);
        if(u!=w)
        {
            add2[Search(w,u)]++;
            sub2[u]++;
        }
        if(v!=w)
        {
            add1[Search(w,v)]++;
            sub1[v]++;
        }
    }
    SumDFS(1,1,add1[1],add2[1]);
    for(int i=0;i<Edge.size();i++)
    {
        int u=Pre[Edge[i].first];
        int v=Pre[Edge[i].second];
        if(u==v)
            cout<<'B';
        else
        if((u==P[v][0]&&Pass1[v]==true)||(v==P[u][0]&&Pass2[u]==true))
            cout<<'R';
        else
            cout<<'L';
    }
}

Compilation message (stderr)

oneway.cpp: In function 'void FindBridge(int, int)':
oneway.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gg[u].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSComponent(int, int)':
oneway.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gg[u].size();i++)
                 ~^~~~~~~~~~~~~
oneway.cpp: In function 'void DFSHigh(int, int)':
oneway.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'void SumDFS(int, int, int, int)':
oneway.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp:156:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                 ~^~~~~~~~~~~~
oneway.cpp: In function 'int Search(int, int)':
oneway.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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