제출 #1197125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197125		aykhn	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3094 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;
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});
  }
  for (int i = 1; i <= n; i++) 
  {
    if (!used[i]) findbr(i, -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});
    }
  }
  fill(dep, dep + n + 1, -1);
  for (int i = 1; i <= n; i++)
  {
    if (dsu.get(i) != i) continue;
    if (dep[i] != -1) continue;
    dfs(i, i);
  }
  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 (u != v)
    {
      if (dep[u] > dep[v])
      {
        res[par[u]] = 0;
        if (dsu.get(ed[par[u]][0]) == u)
        u = dsu.get(ed[par[u]][0]) ^ dsu.get(ed[par[u]][1]) ^ u;
      }
      else 
      {
        res[par[v]] = 1;
        v = dsu.get(ed[par[v]][0]) ^ dsu.get(ed[par[v]][1]) ^ 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;
    //     int X = dsu.get(ed[par[A]][0]), Y = dsu.get(ed[par[A]][1]);
    //     assert(X == A || Y == A);
    //     dsu1.unite(A, X ^ Y ^ A);
    //   }
    //   else 
    //   {
    //     res[par[B]] = 1;
    //     int X = dsu.get(ed[par[B]][0]), Y = dsu.get(ed[par[B]][1]);
    //     assert(X == B || Y == B);
    //     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