Submission #1197110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197110		aykhn	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	2 ms	4928 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;

struct DSU
{
  vector<int> e;
  vector<array<int, 2>> up;
  void init(int n)
  {
    e.assign(n + 1, -1);
    up.assign(n + 1, {0, 0});
  }
  int get(int x)
  {
    if (e[x] < 0) return x;
    return e[x] = get(e[x]);
  }
  int getup(int x)
  {
    return up[get(x)][1];
  }
  void unite(int x, int y)
  {
    x = get(x), y = get(y);
    if (x == y) return;
    if (e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    up[x] = min(up[x], up[y]);
    e[y] = x;
  }
};

int n, R;
vector<array<int, 2>> adj[MXN], g[MXN];
vector<array<int, 2>> ed;
int used[MXN], dep[MXN], bri[MXN], par[MXN];
DSU dsu, dsu1;

int findbr(int a, int prv)
{
  int mn = inf;
  used[a] = 1;
  for (auto &[v, i] : adj[a])
  {
    if (i == prv) continue;
    if (used[v]) 
    {
      mn = min(mn, dep[v]);
      continue;
    }
    dep[v] = dep[a] + 1;
    mn = min(mn, findbr(v, i));
  }
  if (mn >= dep[a] && prv != -1) bri[prv] = 1; 
  return mn;
}
void dfs(int a, int p)
{
  for (auto &[v, i] : g[a])
  {
    if (v == p) continue;
    par[v] = i;
    dep[v] = dep[a] + 1;
    dfs(v, a);
  }
}

void _()
{
  int m;
  cin >> n >> m;
  dsu.init(n), dsu1.init(n);
  for (int i = 0; i < m; i++)
  {
    int u, v;
    cin >> u >> v;
    adj[u].push_back({v, i});
    adj[v].push_back({u, i});
    ed.push_back({u, v});
  }
  findbr(1, -1);
  for (int i = 0; i < m; i++)
  {
    if (!bri[i]) dsu.unite(ed[i][0], ed[i][1]);
  }
  for (int i = 0; i < m; i++)
  {
    if (bri[i]) 
    {
      g[dsu.get(ed[i][0])].push_back({dsu.get(ed[i][1]), i});
      g[dsu.get(ed[i][1])].push_back({dsu.get(ed[i][0]), i});
    }
  }
  R = dsu.get(1);
  dep[R] = 0;
  dfs(R, R);
  for (int i = 1; i <= n; i++) dsu1.up[i] = {dep[i], i};
  string res(m, 'B');
  int q;
  cin >> q;
  while (q--)
  {
    int u, v;
    cin >> u >> v;
    u = dsu.get(u), v = dsu.get(v);
    while (dsu1.getup(u) != dsu1.getup(v))
    {
      int A = dsu1.getup(u), B = dsu1.getup(v); 
      if (dep[A] > dep[B]) 
      {
        res[par[A]] = 0;
        dsu1.unite(A, dsu.get(ed[par[A]][0]) ^ dsu.get(ed[par[A]][1]) ^ A);
      }
      else 
      {
        res[par[B]] = 1;
        dsu1.unite(B, dsu.get(ed[par[B]][0]) ^ dsu.get(ed[par[B]][1]) ^ B);
      }
    }
  }
  for (int i = 0; i < m; i++)
  {
    if (res[i] == 'B') continue;
    int u = dsu.get(ed[i][0]), v = dsu.get(ed[i][1]);
    assert(par[u] == i || par[v] == i);
    if (res[i] == 0)
    {
      if (par[u] == i) res[i] = 'R';
      else res[i] = 'L';
    }
    else
    {
      if (par[u] == i) res[i] = 'L';
      else res[i] = 'R';
    }
  }
  cout << res << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

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