Submission #577132

#	Time	Username	Problem	Language	Result	Execution time	Memory
577132		andrei_boaca	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	68 ms	18584 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n,m,p;
pii keep[100005];
pii edge[100005],sol[100005];
vector<pii> muchii[100005];
int topar[100005];
int par[100005];
bool use[100005];
int nr1[100005],nr2[100005];
int niv[100005],nivmin[100005];
int root=1;
void dfs(int nod)
{
    use[nod]=1;
    if(nod==root)
        niv[nod]=1;
    nivmin[nod]=niv[nod];
    for(auto i:muchii[nod])
    {
        int a=i.first;
        int index=i.second;
        if(index==topar[nod])
            continue;
        if(!use[a])
        {
            niv[a]=niv[nod]+1;
            topar[a]=index;
            dfs(a);
            nr1[nod]+=nr1[a];
            nr2[nod]+=nr2[a];
            if(nivmin[a]<=niv[nod])
                sol[index]={-1,-1};
            else
            {
                if(nr1[a]>nr2[a])
                    sol[index]={a,nod};
                if(nr1[a]<nr2[a])
                    sol[index]={nod,a};
                if(nr1[a]==nr2[a])
                    sol[index]={-1,-1};
            }
            nivmin[nod]=min(nivmin[nod],nivmin[a]);
        }
        else
        {
            sol[index]={-1,-1};
            nivmin[nod]=min(nivmin[nod],niv[a]);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        edge[i]={a,b};
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
    }
    cin>>p;
    for(int i=1;i<=p;i++)
    {
        cin>>keep[i].first>>keep[i].second;
        int a=keep[i].first;
        int b=keep[i].second;
        nr1[a]++;
        nr2[b]++;
    }
    for(int i=1;i<=n;i++)
        if(!use[i])
        {
            root=i;
            dfs(root);
        }
    for(int i=1;i<=m;i++)
    {
        if(sol[i].first==-1)
            cout<<"B";
        else
            if(sol[i].first==edge[i].first)
                cout<<"R";
        else
            cout<<"L";
    }
    return 0;
}

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