Submission #858389

#	Time	Username	Problem	Language	Result	Execution time	Memory
858389		Tenis0206	One-Way Streets (CEOI17_oneway)	C++11	60 / 100	3031 ms	21772 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;

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;
    for(auto it : G[nod])
    {
        if(sel[it.first])
        {
            if(it.second!=nr)
            {
                rez[it.second] = 'B';
            }
            continue;
        }
        solve(it.first,it.second);
    }
    if(!nr)
    {
        return;
    }
    if(r[nod] < lvl[nod])
    {
        rez[nr] = 'B';
        return;
    }
    bool sus = false, jos = false;
    for(auto it : rst)
    {
        int x = it.first;
        int y = it.second;
        if((p[x] < p[nod] || p[x] > u[nod]) && (p[y] >= p[nod] && p[y] <= u[nod]))
        {
            jos = true;
        }
        if((p[y] < p[nod] || p[y] > u[nod]) && (p[x] >= p[nod] && p[x] <= 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: 0 / 40