Submission #1264483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264483		inesfi	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	77 ms	32824 KiB

oneway

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

#define int long long

const int TAILLEMAXI=100*1000+2;
int nbnoeuds,nbaretes,nbpaires;
vector<pair<int,int>> aretes,paires;
vector<pair<int,int>> adja[TAILLEMAXI]; // numar,voisin
vector<bool> essentiel;
int dejavu[TAILLEMAXI],plush[TAILLEMAXI];
int numcompo[TAILLEMAXI];
vector<pair<int,int>> nouvadja[TAILLEMAXI];
vector<int> enfants[TAILLEMAXI];
int enbas[TAILLEMAXI];
int cumu[TAILLEMAXI];
bool vu[TAILLEMAXI];
bool vudfs2[TAILLEMAXI];

int plushaut(int a,int vient,int p){
    //cout<<a<<endl;
    if (dejavu[a]!=-1){
        essentiel[vient]=false;
        //cout<<a<<endl;
        return dejavu[a];
    }
    dejavu[a]=p;
    plush[a]=p;
    for (auto v:adja[a]){
        if (v.first!=vient){
            plush[a]=min(plush[a],plushaut(v.second,v.first,p+1));
        }
    }
    //cout<<a<<endl;
    return plush[a];
}

void dfs(int a,int c){
    if (numcompo[a]!=-1){
        return ;
    }
    numcompo[a]=c;
    for (auto v:adja[a]){
        if (essentiel[v.first]==false){
            dfs(v.second,c);
        }
    }
}

void dfs2(int a,int vient,int pere){
    if (vient!=-1){
        enbas[vient]=a;
        //cout<<"enbas "<<vient<<" = "<<a<<" haut "<<pere<<endl;
    }
    vudfs2[a]=true;
    for (auto v:nouvadja[a]){
        if (v.first!=vient){
            dfs2(v.second,v.first,a);
            enfants[a].push_back(v.second);
        }
    }
}

int dp(int a){
    vu[a]=true;
    for (auto v:enfants[a]){
        cumu[a]+=dp(v);
    }
    return cumu[a];
}

void affiche_essentiel(){
    for (int i=0;i<nbaretes;i++){
        if (essentiel[i]){
            cout<<i<<" deb "<<aretes[i].first<<" fin "<<aretes[i].second<<endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbnoeuds>>nbaretes;
    for (int i=0;i<nbaretes;i++){
        int d,f;
        cin>>d>>f;
        aretes.push_back({d-1,f-1});
        essentiel.push_back(true);
        adja[d-1].push_back({i,f-1});
        adja[f-1].push_back({i,d-1});
    }
    cin>>nbpaires;
    for (int i=0;i<nbpaires;i++){
        int d,f;
        cin>>d>>f;
        paires.push_back({d-1,f-1});
    }
    for (int i=0;i<nbnoeuds;i++){
        dejavu[i]=-1;
        numcompo[i]=-1;
    }
    for (int i=0;i<nbnoeuds;i++){
        if (dejavu[i]==-1){
            plushaut(i,-1,0);
        }
        //cout<<"prof "<<dejavu[i]<<" plush "<<plush[i]<<endl;
    }
    for (int i=0;i<nbaretes;i++){
        pair<int,int> ar=aretes[i];
        if (dejavu[ar.first]<dejavu[ar.second]){
            if (plush[ar.second]<=dejavu[ar.first]){
                essentiel[i]=false;
            }
        }
        else {
            if (plush[ar.first]<=dejavu[ar.second]){
                essentiel[i]=false;
            }
        }
    }
    //affiche_essentiel();
    //return 0;
    int num=0;
    for (int i=0;i<nbnoeuds;i++){
        if (numcompo[i]==-1){
            dfs(i,num);
            num++;
        }
        //cout<<numcompo[i]<<" ";
    }
    //cout<<endl;
    for (int i=0;i<nbaretes;i++){
        if (essentiel[i]){
            nouvadja[numcompo[aretes[i].first]].push_back({i,numcompo[aretes[i].second]});
            nouvadja[numcompo[aretes[i].second]].push_back({i,numcompo[aretes[i].first]});
        }
    }
    for (int i=0;i<num;i++){
        if (vudfs2[i]==false){
            dfs2(i,-1,-1);
        }
    }
    for (auto p:paires){
        cumu[numcompo[p.first]]++;
        cumu[numcompo[p.second]]--;
    }
    for (int i=0;i<num;i++){
        if (vu[i]==false){
            dp(i);
        }
    }
    /*for (int i=0;i<num;i++){
        cout<<cumu[i]<<endl;
    }*/
    for (int i=0;i<nbaretes;i++){
        if (essentiel[i]==false){
            cout<<'B';
        }
        else {
            if (cumu[enbas[i]]==0){
                cout<<'B';
            }
            else if (cumu[enbas[i]]>0){
                if (numcompo[aretes[i].first]==enbas[i]){
                    cout<<'R';
                }
                else {
                    cout<<'L';
                }
            }
            else {
                if (numcompo[aretes[i].first]==enbas[i]){
                    cout<<'L';
                }
                else {
                    cout<<'R';
                }
            }
        }
    }
    return 0;
}

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