oj.uz

Submission #349286

# Submission time Handle Problem Language Result Execution time Memory
349286 2021-01-17T10:32:19 Z doowey One-Way Streets (CEOI17_oneway) C++14
0 / 100
 2 ms 2668 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<pii> T[N];
int tin[N];
int tout[N];
int low[N];
bool use[N];
int u[N], v[N];
int ti;

void dfs(int u, int pp){
    ti++;
    tin[u]=ti;
    low[u]=tin[u];
    for(auto x : T[u]){
        if(tin[x.fi] == 0){
            use[x.se]=true;
            dfs(x.fi,x.se);
            low[u]=min(low[u],low[x.fi]);
        }
        else if(x.se != pp){
            low[u]=min(low[u],tin[x.fi]);
        }
    }
    tout[u]=ti;
}

int out_low[N], out_high[N];
int in_low[N], in_high[N];

char sol[N];

void set_to(int x, int y, int id){
    if(u[id] == x){
        sol[id]='R';
    }
    else{
        sol[id]='L';
    }
    // set id to x->y
}

void dfs2(int u, int pp){
    for(auto x : T[u]){
        if(x.se != pp && use[x.se]){
            dfs2(x.fi,x.se);
            in_low[u]=min(in_low[x.fi],in_low[u]);
            out_low[u]=min(out_low[x.fi],out_low[u]);
            in_high[u]=max(in_high[x.fi],in_high[u]);
            out_high[u]=max(out_high[x.fi],out_high[u]);
            if(tin[u]<low[x.fi]){
                if(in_low[x.fi] < tin[x.fi] || in_high[x.fi] > tout[x.fi]){
                    set_to(u,x.fi,x.se);
                }
                else if(out_low[x.fi] < tin[x.fi] || out_high[x.fi] > tout[x.fi]){
                    set_to(x.fi,u,x.se);
                }
                else{
                    sol[x.se]='B';
                }
            }
            else{
                sol[x.se]='B';
            }
        }
        else if(x.se != pp){
            sol[x.se]='B';
        }
    }
}

int main(){
    fastIO;
    int n, m, p;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ ){
        cin >> u[i] >> v[i];
        T[u[i]].push_back(mp(v[i],i));
        T[v[i]].push_back(mp(u[i],i));
    }
    vector<int> ord;
    for(int i = 1; i <= n; i ++ ){
        if(tin[i] == 0){
            dfs(i,-1);
            ord.push_back(i);
        }
    }
    for(int i = 1; i <= n; i ++ ){
        out_low[i] = n + 1;
        in_low[i] = n + 1;
    }
    int xi, yi;
    cin >> p;
    for(int i = 1; i <= p ; i ++ ){
        cin >> xi >> yi;
        out_low[xi]=min(out_low[xi],tin[yi]);
        out_high[xi]=max(out_high[xi],tin[yi]);
        in_low[yi]=min(in_low[yi],tin[xi]);
        in_high[yi]=min(in_high[yi],tin[xi]);
    }
    for(auto x : ord)
    dfs2(x,-1);
    for(int i = 1; i <= m ; i ++ ){
        cout << sol[i];
    }
    cout << "\n";
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -