Submission #1309846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309846		SSKMF	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	2 ms	332 KiB

oneway

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

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

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)
{
    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 { rezultat[abs(vecin.second) - 1] = (vecin.second < 0 ? 'R' : 'L'); }
        }
    }
}

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);
    }

    Parcurgere(1 , 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[nod_1]++;
        termen[nod_2]--;
    }

    Build(1 , 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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40