oj.uz

Submission #1062115

# Submission time Handle Problem Language Result Execution time Memory
1062115 2024-08-16T19:18:04 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 13136 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};
    }

    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 5 ms 5156 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 5 ms 5156 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 95 ms 10068 KB Output is correct
12 Correct 120 ms 10836 KB Output is correct
13 Correct 190 ms 11732 KB Output is correct
14 Correct 225 ms 12112 KB Output is correct
15 Correct 214 ms 11856 KB Output is correct
16 Correct 57 ms 9912 KB Output is correct
17 Correct 172 ms 12880 KB Output is correct
18 Correct 119 ms 10112 KB Output is correct
19 Correct 261 ms 13068 KB Output is correct
20 Correct 207 ms 10688 KB Output is correct
21 Correct 180 ms 10212 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 5 ms 5156 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 95 ms 10068 KB Output is correct
12 Correct 120 ms 10836 KB Output is correct
13 Correct 190 ms 11732 KB Output is correct
14 Correct 225 ms 12112 KB Output is correct
15 Correct 214 ms 11856 KB Output is correct
16 Correct 57 ms 9912 KB Output is correct
17 Correct 172 ms 12880 KB Output is correct
18 Correct 119 ms 10112 KB Output is correct
19 Correct 261 ms 13068 KB Output is correct
20 Correct 207 ms 10688 KB Output is correct
21 Correct 180 ms 10212 KB Output is correct
22 Execution timed out 3031 ms 13136 KB Time limit exceeded
23 Halted 0 ms 0 KB -