Submission #92322

#	Time	Username	Problem	Language	Result	Execution time	Memory
92322		Bodo171	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	160 ms	25220 KiB

oneway

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
char ans[nmax];
vector<int> v[nmax],ag[nmax];
int tt[nmax],rg[nmax],dad[nmax],bc[nmax],st[nmax],lnod[nmax],rnod[nmax],l[nmax],r[nmax],low[nmax],lev[nmax],a[nmax],b[nmax],to_dad[nmax],sus[nmax],edg[nmax],marked[nmax];
int n,m,q,bcc,u,nr,i,x,y,mu;
int finds(int x)
{
    int y=x,aux;
    while(x!=tt[x])
        x=tt[x];
    while(y!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void unite(int A,int B)
{
    if(rg[A]<rg[B]) swap(A,B);
    tt[B]=A;
    rg[A]+=rg[B];
}
void mark_bcc(int x)
{
    bc[st[u]]=bcc;
    for(int i=0;i<ag[st[u]].size();i++)
    {
        dad[ag[st[u]][i]]=bcc;
    }
    if(st[u]==x)
    {
        u--;
        return;
    }
    u--;
    mark_bcc(x);
}
void dfs(int x)
{
    int nod=0,mu=0;
    low[x]=n+1;lnod[x]=++nr;st[++u]=x;
    for(int i=0;i<v[x].size();i++)
    {
        mu=v[x][i];
        nod=(a[mu]^b[mu]^x);
        if(!lev[nod])
        {
            lev[nod]=lev[x]+1;
            edg[nod]=mu;
            dfs(nod);
            if(low[nod]>lev[x])
            {
                ++bcc;
                mark_bcc(nod);
                l[bcc]=lnod[nod];
                r[bcc]=rnod[nod];
                to_dad[bcc]=mu;
                ag[x].push_back(bcc);
            }
            low[x]=min(low[x],low[nod]);
        }
        else
        {
            if(mu!=edg[x])
                low[x]=min(low[x],lev[nod]);
        }
    }
    rnod[x]=nr;
}
bool cup(int A,int B)
{
    return (l[A]<=l[B]&&r[B]<=r[A]);
}
void mark(int x,int oth,int col)
{
    while(!cup(x,oth))
    {
        marked[x]=col;
        sus[finds(x)]=sus[finds(dad[x])];
        unite(finds(x),finds(dad[x]));
        x=sus[finds(x)];
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
    for(int S=1;S<=n;S++)
        if(!lev[S])
    {
        lev[S]=1;
        dfs(S);
        if(u)
          {
              ++bcc;
              l[bcc]=lnod[st[1]];
              r[bcc]=rnod[st[1]];
              mark_bcc(st[1]);
          }
    }
    for(i=1;i<=bcc;i++)
        tt[i]=i,rg[i]=1,sus[i]=i;
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>x>>y;
        x=bc[x];y=bc[y];
        mark(x,y,1);
        mark(y,x,2);
    }
    for(i=0;i<m;i++)
        ans[i]='B';
    for(i=1;i<=bcc;i++)
        if(marked[i])
    {
        mu=to_dad[i];
        if((bc[a[mu]]==i&&marked[i]==1)||(marked[i]==2&&bc[a[mu]]!=i)) ans[mu-1]='R';
        else ans[mu-1]='L';
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void mark_bcc(int)':
oneway.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ag[st[u]].size();i++)
                 ~^~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

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