oj.uz

Submission #595746

# Submission time Handle Problem Language Result Execution time Memory
595746 2022-07-14T05:49:36 Z 1bin One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, m, P, a[NMAX], b[NMAX], u, v, vis[NMAX];
int dfsn[NMAX], low[NMAX], t, cl[NMAX], ans[NMAX], chk[NMAX];
vector<pair<int, int>> adj[NMAX], g[NMAX];

void dfs(int x, int e){
    dfsn[x] = low[x] = ++t;
    for(auto& [nx, ix] : adj[x]){
        if(ix == e) continue;
        if(!dfsn[nx]){
            dfs(nx, ix);
            low[x] = min(low[x], low[nx]);
        }
        else if(dfsn[nx] < dfsn[x]) low[x] = min(low[x], dfsn[nx]);
    }
    return;
}

void dfs2(int x, int c){
    cl[x] = c;
    for(auto& [nx, ix] : adj[x]){
        if(cl[nx]) continue;
        if(low[nx] > dfsn[x]) {
            g[c].emplace_back(++t, ix);
            g[t].emplace_back(c, ix);
            dfs2(nx, t);
        }
        else dfs2(nx, c);
    }
    return;
}

void dfs3(int x){
    vis[x] = 1;
    for(auto& [nx, ix] : g[x]){
        if(vis[nx]) continue;
        dfs3(nx);
        if(chk[nx] > 0) ans[ix] = 1;
        else if(chk[nx] < 0) ans[ix] = -1;
        chk[x] += chk[nx];
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        adj[a[i]].emplace_back(b[i], i);
        adj[b[i]].emplace_back(a[i], i);
    }
    
    for(int i = 1; i <= n; i++)
        if(!dfsn[i]) dfs(i, -1);
    t = 0;
    for(int i = 1; i <= n; i++)
        if(!cl[i]) dfs2(i, ++t);
        
    cin >> P;
    while(P--){
        cin >> u >> v;
        chk[cl[u]]++; chk[cl[v]]--;
    }
    
    for(int i = 1; i <= t; i++)
        if(!vis[i]) dfs3(i);
        
    for(int i = 0; i < m; i++){
        if(!ans[i]) cout << 'B';
        else cout << (ans[i] > 0 ? 'R' : 'L');
    }
    return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto& [nx, ix] : adj[x]){
      |               ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto& [nx, ix] : adj[x]){
      |               ^
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto& [nx, ix] : g[x]){
      |               ^

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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