Submission #858394

#	Time	Username	Problem	Language	Result	Execution time	Memory
858394		Tenis0206	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	91 ms	27336 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int oo = INT_MAX;

int n,m,k;

pair<int,int> e[nmax + 5];
vector<pair<int,int>> G[nmax + 5];

bool sel[nmax + 5];

int lvl[nmax + 5], r[nmax + 5];

int p[nmax + 5], u[nmax + 5];

vector<pair<int,int>> rst;

vector<int> out[nmax + 5], in[nmax + 5];

int cnt = 0;

char rez[nmax + 5];

vector<int> l_sel;

int Min_px[nmax + 5], Max_px[nmax + 5], Min_py[nmax + 5], Max_py[nmax + 5];

void dfs(int nod, int nr = 0)
{
    l_sel.push_back(nod);
    p[nod] = (++cnt);
    sel[nod] = true;
    r[nod] = lvl[nod];
    for(auto it : G[nod])
    {
        if(sel[it.first])
        {
            if(it.second!=nr)
            {
                r[nod] = min(r[nod], lvl[it.first]);
            }
            continue;
        }
        lvl[it.first] = 1 + lvl[nod];
        dfs(it.first,it.second);
        r[nod] = min(r[nod], r[it.first]);
    }
    u[nod] = cnt;
}

void solve(int nod, int nr = 0)
{
    sel[nod] = true;
    Min_px[nod] = oo, Max_px[nod] = 0, Min_py[nod] = oo, Max_py[nod] = 0;
    for(auto x : in[nod])
    {
        Min_px[nod] = min(Min_px[nod], p[x]);
        Max_px[nod] = max(Max_px[nod], p[x]);
    }
    for(auto y : out[nod])
    {
        Min_py[nod] = min(Min_py[nod], p[y]);
        Max_py[nod] = max(Max_py[nod], p[y]);
    }
    for(auto it : G[nod])
    {
        if(sel[it.first])
        {
            if(it.second!=nr)
            {
                rez[it.second] = 'B';
            }
            continue;
        }
        solve(it.first,it.second);
        Min_px[nod] = min(Min_px[nod], Min_px[it.first]);
        Max_px[nod] = max(Max_px[nod], Max_px[it.first]);
        Min_py[nod] = min(Min_py[nod], Min_py[it.first]);
        Max_py[nod] = max(Max_py[nod], Max_py[it.first]);
    }
    if(!nr)
    {
        return;
    }
    if(r[nod] < lvl[nod])
    {
        rez[nr] = 'B';
        return;
    }
    bool sus = false, jos = false;
    if(Min_px[nod] < p[nod] || Max_px[nod] > u[nod])
    {
        jos = true;
    }
    if(Min_py[nod] < p[nod] || Max_py[nod] > u[nod])
    {
        sus = true;
    }
    if(jos)
    {
        if(e[nr].second == nod)
        {
            rez[nr] = 'R';
        }
        else
        {
            rez[nr] = 'L';
        }
    }
    if(sus)
    {
        if(e[nr].second == nod)
        {
            rez[nr] = 'L';
        }
        else
        {
            rez[nr] = 'R';
        }
    }
    if(!sus && !jos)
    {
        rez[nr] = 'B';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        e[i] = {x,y};
        if(x==y)
        {
            rez[i] = 'B';
            continue;
        }
        G[x].push_back({y,i});
        G[y].push_back({x,i});
    }
    cin>>k;
    for(int i=1; i<=k; i++)
    {
        int x,y;
        cin>>x>>y;
        out[x].push_back(y);
        in[y].push_back(x);
        rst.push_back({x,y});
    }
    for(int i=1; i<=n; i++)
    {
        if(!sel[i])
        {
            l_sel.clear();
            dfs(i);
            for(auto it : l_sel)
            {
                sel[it] = false;
            }
            solve(i);
        }
    }
    cout<<rez+1<<'\n';
    return 0;
}

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