oj.uz

답안 #974177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974177 2024-05-03T04:25:52 Z duckindog One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 8540 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m, p;
int from[N], to[N];
vector<pair<int, bool>> ad[N];
int a[N], b[N];
namespace BCC { 
  vector<int> ad[N];
  int low[N], num[N], it;
  stack<int> st;
  int bcc[N], cc;
  void dfs(int u, int p = -1) { 
    low[u] = num[u] = ++it;
    st.push(u);
    
    bool pass = false;
    for (const auto& v : ad[u]) { 
      if (bcc[v] || v == p && !pass) { 
        pass = true;
        continue;
      }

      if (!low[v]) { 
        dfs(v, u);
        low[u] = min(low[u], low[v]);
      } else low[u] = min(low[u], num[v]);
    }
    
    if (low[u] == num[u]) { 
      bcc[u] = ++cc;
      while (st.top() != u) { 
        bcc[st.top()] = cc;
        st.pop();
      } st.pop();
    }
  }
}

int st[N], ed[N], it;
int root[N], par[N];
bool mk[N], vst[N];
void dfs(int u, int p = - 1) { 
  st[u] = ++it;
  root[u] = u;
  for (const auto& [v, way] : ad[u]) { 
    if (v == p) continue;
    par[v] = u;
    mk[v] = way;
    dfs(v, u);
  }
  ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= m; ++i) cin >> from[i] >> to[i];
  cin >> p;
  for (int i = 1; i <= p; ++i) cin >> a[i] >> b[i];

  for (int i = 1; i <= m; ++i) { 
    int u = from[i], v = to[i];
    BCC::ad[u].push_back(v);
    BCC::ad[v].push_back(u);
  }

  BCC::dfs(1);
  
  for (int i = 1; i <= m; ++i) { 
    int u = BCC::bcc[from[i]], v = BCC::bcc[to[i]];
    if (u == v) continue;
    ad[u].push_back({v, true});
    ad[v].push_back({u, false});
  }
  
  dfs(par[1] = 1);
  
  for (int i = 1; i <= p; ++i) { 
    int u = BCC::bcc[a[i]], v = BCC::bcc[b[i]];
    if (u == v) continue;
    for (int t = 1; t >= 0; --t) {
      vector<int> vt;
      while (!anc(par[root[u]], v)) { 
        vt.push_back(u);
        u = par[root[u]];
      } vt.push_back(u);
      for (const auto& x : vt) { 
        root[x] = u;
        mk[x] ^= t;
        vst[x] = true;
      }
      swap(u, v);
    }
  }
  
  for (int i = 1; i <= m; ++i) { 
    int u = from[i], v = to[i];

    int x = BCC::bcc[u], y = BCC::bcc[v];
    
    if (x == y) cout << "B";
    else if (anc(x, y)) cout << (!vst[y] ? 'B' : mk[y] ? 'R' : 'L');
    else cout << (!vst[x] ? 'B' : mk[x] ? 'R' : 'L');
  }
  cout << "\n";
}

Compilation message

oneway.cpp: In function 'void BCC::dfs(int, int)':
oneway.cpp:21:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   21 |       if (bcc[v] || v == p && !pass) {
      |                     ~~~~~~~^~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -