oj.uz

답안 #1062059

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062059 2024-08-16T18:04:26 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 4956 KB 
#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};
    }

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

    int process=dfstree(1,-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;

}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:89:9: warning: unused variable 'process' [-Wunused-variable]
   89 |     int process=dfstree(1,-1,1);
      |         ^~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -