oj.uz

Submission #886386

# Submission time Handle Problem Language Result Execution time Memory
886386 2023-12-12T02:35:06 Z Zero_OP One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3 ms 12892 KB 
#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], parID[N], lift[20][N];
bool vst[N];

void dfsTree(int u, int lastID){
  vst[u] = true;
  for(int id : G[u]) if(id != lastID){
    int v = aNodes[id] ^ bNodes[id] ^ u;
    h[v] = h[u] + 1;
    parID[v] = id;
    lift[0][v] = u;
    for(int i = 1; i <= 17; ++i){
      lift[i][v] = lift[i - 1][lift[i - 1][v]];
    }

    dfsTree(v, id);
  }
}

int getLCA(int u, int v){
  if(h[u] != h[v]){
    if(h[u] < h[v]) swap(u, v);
    for(int i = 17; i >= 0; --i){
      if(h[u] - (1 << i) >= h[v]){
        u = lift[i][u];
      }
    }
  }
  if(u == v) return u;
  for(int i = 17; i >= 0; --i){
    if(lift[i][u] != lift[i][v]){
      u = lift[i][u];
      v = lift[i][v];
    }
  }
  return lift[0][u];
}

void compute(int u, int v){
  int lca = getLCA(u, v);

  while(h[u] != h[lca]){
    int id = parID[u];
//    cout << id << '\n';
    if(ans[id] > 0) break;
    ans[id] = (aNodes[id] == u ? 2 : 1);
    u = lift[0][u];
  }

  while(h[v] != h[lca]){
    int id = parID[v];
//    cout << "!" << id << '\n';
    if(ans[id] > 0) break;
    ans[id] = (aNodes[id] == v ? 1 : 2);
    v = lift[0][v];
  }
}

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]){
      G[id[u]].push_back(i);
      G[id[v]].push_back(i);
    }
  }

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

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

  for(int i = 1; i <= m; ++i){
    if(ans[i] == 0) cout << 'B';
    else if(ans[i] == 1) 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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Incorrect 2 ms 12892 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Incorrect 2 ms 12892 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Incorrect 2 ms 12892 KB Output isn't correct
5 Halted 0 ms 0 KB -