Submission #1062115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062115		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3031 ms	13136 KiB

oneway

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

#define ll long long
#define pb push_back
const int N=100100;

int n,m,p,x,y;
vector<vector<pair<int,int>>>graph(N);
vector<pair<int,int>>directions(N);
vector<int>dp(N);
vector<int>bridges(N);
int text[N];

int visitados[N];

int dfstree(int pos, int prev, int altura){
    //cout<<pos<<" POS"<<endl;
    visitados[pos]=1;
    dp[pos]=altura;
    for(int i=0;i<int(graph[pos].size());i++){
        if(graph[pos][i].second==prev){

            continue;
        }
        if(visitados[graph[pos][i].first]==2){
            continue;
        }
        if(visitados[graph[pos][i].first]==1){
            dp[pos]=min(dp[graph[pos][i].first],dp[pos]);
            continue;
        }

        dp[pos]=min(dfstree(graph[pos][i].first, graph[pos][i].second,altura+1),dp[pos]);
    }
    visitados[pos]=2;

    if(prev != -1 && dp[pos]>=altura){
        //cout<<prev<<endl;
        bridges[prev]=1;
    }
    return dp[pos];
}

int dfs(int pos,int finalpos){
    visitados[pos]=1;
    if(pos==finalpos){
        return 1;
    }
    //cout<<pos<<" POOOOOS"<<endl;
    for(int i=0;i<int(graph[pos].size());i++){
        //cout<<visitados[pos]<<endl;
        if (visitados[graph[pos][i].first]==1){
            continue;
        }
        int index=graph[pos][i].second;
        int passfinal=dfs(graph[pos][i].first,finalpos);
        if(passfinal==1){
            if(bridges[index]==1){
                if(directions[index].first==pos && directions[index].second==graph[pos][i].first){
                    text[index]=1;
                }else{
                    text[index]=2;
                }
            }
            return 1;
        }
    }


    return 0;

}


int main(){

    cin>>n >> m;

    for(int i=1;i<=m;i++){
        int a,b; cin >> a >> b;
        graph[a].pb({b,i});
        graph[b].pb({a,i});
        directions[i]={a,b};
    }

    for(int i = 0 ; i <= m ; i ++ )bridges[i] = 0;

    memset(visitados,-1,sizeof(visitados));

    for(int i = 1 ; i<= n ; i ++){
        if(visitados[i] == -1)dfstree(i, -1, 1);
    }



    cin >> p;

    memset(text,-1, sizeof text );
    while(p--){
        cin>>x>>y;
        memset(visitados,-1,sizeof(visitados));
        dfs(x,y);

    }

    for(int i=1;i<=m;i++){
        if(text[i]==1){
            cout<<"R";
            continue;
        }
        if(text[i]==2){
            cout<<"L";
            continue;
        }
        cout<<"B";
    }
    cout<<endl;

}

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