Submission #887084

#	Time	Username	Problem	Language	Result	Execution time	Memory
887084		maxFedorchuk	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	272 ms	42448 KiB

oneway

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

const long long MX=1e5+10;

vector < pair < long long , long long > > mas[MX];
map < pair < long long , long long > , long long > reb;
pair < long long , long long > rb[MX];

vector < long long > mosty_in;
long long real_mosty[MX];

long long tin[MX],tou[MX];
long long timer=0;

void CNTMOST(long long zar,long long mun)
{
    timer++;
    tin[zar]=timer;
    tou[zar]=timer;

    for(auto u:mas[zar])
    {
        if(mun==u.first)
        {
            continue;
        }

        if(tin[u.first]==0)
        {
            CNTMOST(u.first,zar);
            tou[zar]=min(tou[zar],tou[u.first]);

            if(tou[u.first]>tin[zar])
            {
                mosty_in.push_back(u.second);
            }
        }
        else
        {
            tou[zar]=min(tou[zar],tin[u.first]);
        }
    }

    return;
}

long long vis[MX];
long long tmm=0;

void DFS(long long zar)
{
    vis[zar]=tmm;
    for(auto u:mas[zar])
    {
        if(!vis[u.first] && real_mosty[u.second]==0)
        {
            DFS(u.first);
        }
    }

    return;
}

long long prfs[MX];
long long vis2[MX];

map < pair < long long , long long > , long long > res2;

void DFS2(long long zar,long long mun)
{
    vis2[zar]=1;

    for(auto u:mas[zar])
    {
        if(u.first!=mun)
        {
            DFS2(u.first,zar);
            prfs[zar]+=prfs[u.first];
        }
    }

    if(prfs[zar]!=0)
    {
        if(prfs[zar]>0)
        {
            res2[{zar,mun}]=1;
        }
        else
        {
            res2[{mun,zar}]=1;
        }
    }

    return;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,m;
    cin>>n>>m;

    for(long long i=1;i<=m;i++)
    {
        cin>>rb[i].first>>rb[i].second;

        if(rb[i].first!=rb[i].second)
        {
            if(reb.find({rb[i].first,rb[i].second})==reb.end())
            {
                mas[rb[i].first].push_back({rb[i].second,i});
                mas[rb[i].second].push_back({rb[i].first,i});
            }
        }

        reb[{rb[i].first,rb[i].second}]++;
        reb[{rb[i].second,rb[i].first}]++;
    }

    for(long long i=1;i<=n;i++)
    {
        if(tin[i]==0)
        {
            CNTMOST(i,0);
        }
    }

    for(auto u:mosty_in)
    {
        if(reb[{rb[u].first,rb[u].second}]==1)
        {
            real_mosty[u]=1;
        }
    }


    for(long long i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            tmm++;
            DFS(i);
        }
    }

    for(long long i=1;i<=n;i++)
    {
        mas[i].clear();
    }

    for(long long i=1;i<=m;i++)
    {
        if(real_mosty[i])
        {
            mas[vis[rb[i].first]].push_back({vis[rb[i].second],i});
            mas[vis[rb[i].second]].push_back({vis[rb[i].first],i});
        }
    }

    long long q;
    cin>>q;

    long long a,b;
    while(q--)
    {
        cin>>a>>b;

        prfs[vis[a]]++;
        prfs[vis[b]]--;
    }

    for(long long i=1;i<=n;i++)
    {
        if(vis2[i]==0)
        {
            DFS2(i,0);
        }
    }

    for(long long i=1;i<=m;i++)
    {
        if(!real_mosty[i])
        {
            cout<<"B";
            continue;
        }

        if(res2.find({vis[rb[i].first],vis[rb[i].second]})!=res2.end())
        {
            cout<<"R";
            continue;
        }

        if(res2.find({vis[rb[i].second],vis[rb[i].first]})!=res2.end())
        {
            cout<<"L";
        }
        else
        {
            cout<<"B";
        }
    }

    cout<<"\n";
    return 0;
}

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