oj.uz

Submission #349284

# Submission time Handle Problem Language Result Execution time Memory
349284 2021-01-17T10:30:28 Z doowey One-Way Streets (CEOI17_oneway) C++14
0 / 100
 7 ms 3432 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];
int u[N], v[N];
bool bridge[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){
            dfs(x.fi,x.se);
            low[u]=min(low[u],low[x.fi]);
            if(tin[u] < low[x.fi]){
                bridge[x.se]=true;
            }
        }
        else if(x.se != pp){
            low[u]=min(low[u],tin[x.fi]);
        }
    }
    tout[u]=ti;
}


int las[N];
int idx[N];

void dfs(int u){
    for(auto x : T[u]){
        if(las[x.fi] == -1){
            las[x.fi]=u;
            idx[x.fi]=x.se;
            dfs(x.fi);
        }
    }
}

char sol[N];

void setd(int xi, int yi, int id){
    if(xi == u[id]){
        sol[id]='R';
    }
    else{
        sol[id]='L';
    }
}

int main(){
    fastIO;
    freopen("in.txt","r",stdin);
    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));
    }
    for(int i = 1; i <= n; i ++ ){
        if(tin[i] == 0){
            dfs(i,-1);
        }
    }
    for(int i = 1; i <= m; i ++ ){
        sol[i]='B';
    }
    cin >> p;
    int xi, yi;
    for(int i = 1; i <= p ; i ++ ){
        cin >> xi >> yi;
        for(int j = 1; j <= n; j ++ ){
            las[j]=-1;
            idx[j]=-1;
        }
        las[xi]=0;
        dfs(xi);
        while(yi != xi){
            if(bridge[idx[yi]])
                setd(las[yi],yi,idx[yi]);
            yi = las[yi];
        }
    }
    for(int i = 1; i <= m ; i ++ ){
        cout << sol[i];
    }
    cout << "\n";
    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     freopen("in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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