Submission #595759

#	Time	Username	Problem	Language	Result	Execution time	Memory
595759		1bin	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	122 ms	23556 KiB

oneway

#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], f[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]){
            if(chk[nx] > 0 && nx == cl[a[ix]] || chk[nx] < 0 && x == cl[a[ix]]) ans[ix] = 1;
            else 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];
        f[i] = 1;
        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 (stderr)

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]){
      |               ^
oneway.cpp:45:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |             if(chk[nx] > 0 && nx == cl[a[ix]] || chk[nx] < 0 && x == cl[a[ix]]) ans[ix] = 1;
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40