Submission #1309855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309855		SSKMF	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	70 ms	16264 KiB

oneway

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

vector < pair <int , int> > adiacenta[100001] , __adiacenta[100001];
int componenta[100001] , stiva[100001] , moment[100001] , termen[100001];
char rezultat[100001];
bool vizitat[100001];

inline int Parcurgere (const int nod , const int sursa)
{
    bool gasit = false;
    stiva[++stiva[0]] = nod;
    int minim_accesibil = (moment[nod] = ++moment[0]);
    for (auto& vecin : adiacenta[nod]) {
        if (vecin.first == sursa && !gasit)
            { gasit = true; continue; }
        if (!moment[vecin.first])
            { minim_accesibil = min(minim_accesibil , Parcurgere(vecin.first , nod)); }
        else
            { minim_accesibil = min(minim_accesibil , moment[vecin.first]); }
    }

    if (minim_accesibil == moment[nod])
    {
        componenta[0]++;
        while (true)
        {
            componenta[stiva[stiva[0]]] = componenta[0];
            if (stiva[stiva[0]--] == nod)
                { break; }
        }
    }

    return minim_accesibil;
}

inline void Build (const int nod , const int sursa)
{
    vizitat[nod] = true;
    for (auto& vecin : __adiacenta[nod]) {
        if (vecin.first != sursa)
        {
            Build(vecin.first , nod);

            termen[nod] += termen[vecin.first];
            if (termen[vecin.first] < 0) { rezultat[abs(vecin.second) - 1] = (vecin.second < 0 ? 'L' : 'R'); }
            else if (termen[vecin.first] > 0) { rezultat[abs(vecin.second) - 1] = (vecin.second < 0 ? 'R' : 'L'); }
            else { rezultat[abs(vecin.second) - 1] = 'B'; }
        }
    }
}

inline void Solve ()
{
    int numar_noduri , numar_muchii;
    cin >> numar_noduri >> numar_muchii;

    for (int indice = 1 ; indice <= numar_muchii ; indice++)
    {
        int nod[2]; cin >> nod[0] >> nod[1];
        adiacenta[nod[0]].emplace_back(nod[1] , indice);
        adiacenta[nod[1]].emplace_back(nod[0] , -indice);
    }

    for (int nod = 1 ; nod <= numar_noduri ; nod++) {
        if (!moment[nod])
            { Parcurgere(nod , 0); }
    }
    
    for (int nod = 1 ; nod <= numar_noduri ; nod++) {
        for (auto& vecin : adiacenta[nod]) {
            if (componenta[nod] == componenta[vecin.first])
                { rezultat[abs(vecin.second) - 1] = 'B'; }
            else
                { __adiacenta[componenta[nod]].emplace_back(componenta[vecin.first] , vecin.second); }
        }
    }

    int numar_operatii;
    cin >> numar_operatii;

    while (numar_operatii--)
    {
        int nod_1 , nod_2;
        cin >> nod_1 >> nod_2;

        termen[componenta[nod_1]]++;
        termen[componenta[nod_2]]--;
    }

    for (int nod = 1 ; nod <= componenta[0] ; nod++) {
        if (!vizitat[nod])
            { Build(nod , 0); }
    }

    cout << rezultat;
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_teste = 1;
    // cin >> numar_teste;
    while (numar_teste--)
        { Solve(); }

    return 0;
}

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