Submission #886396

#	Time	Username	Problem	Language	Result	Execution time	Memory
886396		Zero_OP	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	56 ms	23376 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
  if(a > b) return a = b, true;
  return false;
}

template<class T> bool maximize(T& a, T b){
  if(a < b) return a = b, true;
  return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 1e5 + 5;

int n, m, ans[N], low[N], num[N], aNodes[N], bNodes[N], uNodes[N], vNodes[N], id[N], timerDFS, timerSCC;
vector<int> g[N], G[N];
stack<int> st;

void dfsTarjan(int u, int lastID){
  low[u] = num[u] = ++timerDFS;
  st.push(u);
  for(int id : g[u]) if(id != lastID) {
    int v = uNodes[id] ^ vNodes[id] ^ u;
    if(num[v]) minimize(low[u], num[v]);
    else{
      dfsTarjan(v, id);
      minimize(low[u], low[v]);
    }
  }

  if(low[u] == num[u]){
    ++timerSCC;
    do{
      int v = st.top(); st.pop();
      low[v] = num[v] = N;
      id[v] = timerSCC;
    } while(!id[u]);
  }
}

int h[N], dp[N];
bool vst[N];

void dfsSolve(int u, int lastID){
  vst[u] = true;
  for(int id : G[u]) if(id != lastID){
    int v = aNodes[id] ^ bNodes[id] ^ u;
    dfsSolve(v, id);
    dp[u] += dp[v];

    if(dp[v] == 0){
      ans[id] = 0;
    }
    else if(dp[v] > 0){
      if(v == aNodes[id]) ans[id] = 1;
      else ans[id] = 2;
    }
    else{
      if(v == aNodes[id]) ans[id] = 2;
      else ans[id] = 1;
    }
  }
}

void Zero_OP(){
  cin >> n >> m;
  for(int i = 1; i <= m; ++i){
    int u, v;
    cin >> u >> v;
    uNodes[i] = u, vNodes[i] = v;
    g[u].push_back(i);
    g[v].push_back(i);
  }

  for(int i = 1; i <= n; ++i){
    if(!num[i]){
      dfsTarjan(i, -1);
    }
  }

  for(int i = 1; i <= m; ++i){
    int u = uNodes[i], v = vNodes[i];
    aNodes[i] = id[u], bNodes[i] = id[v];
    if(id[u] != id[v]){
      ans[i] = -1;
      G[id[u]].push_back(i);
      G[id[v]].push_back(i);
    }
    else ans[i] = 0;
  }

  int q; cin >> q;
  while(q--){
    int x, y;
    cin >> x >> y;
    x = id[x], y = id[y];
    ++dp[x];
    --dp[y];
  }

  for(int i = 1; i <= timerSCC; ++i){
    if(!vst[i]){
      dfsSolve(i, -1);
    }
  }

  for(int i = 1; i <= m; ++i){
    if(ans[i] == 0) cout << 'B';
    else if(ans[i] == 2) cout << 'L';
    else cout << 'R';
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  #define task "antuvu"
  if(fopen(task".inp", "r")){
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
  }

  Zero_OP();

  return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:129:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:130:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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