oj.uz

Submission #974198

# Submission time Handle Problem Language Result Execution time Memory
974198 2024-05-03T05:52:05 Z duckindog One-Way Streets (CEOI17_oneway) C++17
100 / 100
 79 ms 24828 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 par[N], d[N];
bool mk[N], vst[N];
void dfs(int u, int p = - 1) { 
  st[u] = ++it;
  for (const auto& [v, way] : ad[u]) { 
    if (v == p) continue;
    par[v] = u;
    d[v] = d[u] + 1;
    mk[v] = way;
    dfs(v, u);
  }
  ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }

int id[N];
int root(int u) { return !id[u] ? u : id[u] = root(id[u]); }
void add(int u, int v) { 
  u = root(u); v = root(v);
  if (u == v) return;
  if (d[u] > d[v]) swap(u, v);
  id[v] = u;
}

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);
  }

  for (int i = 1; i <= n; ++i) if (!BCC::low[i]) BCC::dfs(i);
  
  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});
  }

  for (int i = 1; i <= n; ++i) if (!par[i]) dfs(par[i] = i);
  
  for (int i = 1; i <= p; ++i) { 
    int u = BCC::bcc[a[i]], v = BCC::bcc[b[i]];
    u = root(u); v = root(v);
    if (u == v) continue;
    for (int t = 1; t >= 0; --t) {
      vector<int> vt;
      while (!anc(u, v)) { 
        vt.push_back(u);
        u = root(par[root(u)]);
      } 
      
      for (const auto& x : vt) { 
        add(x, vt.end()[-1]);
        if (!vst[x]) 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7052 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7052 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 23 ms 12116 KB Output is correct
12 Correct 27 ms 13440 KB Output is correct
13 Correct 37 ms 14676 KB Output is correct
14 Correct 34 ms 16208 KB Output is correct
15 Correct 37 ms 16848 KB Output is correct
16 Correct 43 ms 17672 KB Output is correct
17 Correct 40 ms 20048 KB Output is correct
18 Correct 46 ms 18004 KB Output is correct
19 Correct 46 ms 21332 KB Output is correct
20 Correct 26 ms 13136 KB Output is correct
21 Correct 27 ms 13012 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7052 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 23 ms 12116 KB Output is correct
12 Correct 27 ms 13440 KB Output is correct
13 Correct 37 ms 14676 KB Output is correct
14 Correct 34 ms 16208 KB Output is correct
15 Correct 37 ms 16848 KB Output is correct
16 Correct 43 ms 17672 KB Output is correct
17 Correct 40 ms 20048 KB Output is correct
18 Correct 46 ms 18004 KB Output is correct
19 Correct 46 ms 21332 KB Output is correct
20 Correct 26 ms 13136 KB Output is correct
21 Correct 27 ms 13012 KB Output is correct
22 Correct 79 ms 21236 KB Output is correct
23 Correct 64 ms 19068 KB Output is correct
24 Correct 68 ms 19172 KB Output is correct
25 Correct 61 ms 24828 KB Output is correct
26 Correct 62 ms 20816 KB Output is correct
27 Correct 63 ms 19280 KB Output is correct
28 Correct 21 ms 10072 KB Output is correct
29 Correct 37 ms 13724 KB Output is correct
30 Correct 43 ms 14064 KB Output is correct
31 Correct 40 ms 14496 KB Output is correct
32 Correct 43 ms 17908 KB Output is correct