제출 #1059189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059189		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	92 ms	42896 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair <int,int> pii;

const ll N = 1e5 + 5;
const ll S = 2010;
const ll LOG_N = 18;
const ll oo = 1e16+7;
const ll mod = 2e9 + 7;

char ans[N];
pii edges[N];
vector <vector<pii>> bridge_tree;
int up[N], down[N];
int tin[N], tout[N];
int st[N][20];
int visi[N];
int cnt = 0;

struct tarjan_tree {
  int n;
  vector<vector<int>> comps;
  vector<vector<pii>> g;
  vector<pair<pii, int>> bridge;
  vector<int> id, art;
  tarjan_tree(int n) : n(n), g(n+1), id(n+1), art(n+1) {}
  void add_edge(vector<vector<pii>> &g, int u, int v, int idx) { /// nodes from [1, n]
    g[u].push_back({v, idx});
    g[v].push_back({u, idx});
  }
  void add_edge(int u, int v, int idx) { add_edge(g, u, v, idx); }
  void tarjan(bool with_bridge) {
    vector<int> dfn(n+1), low(n+1);
    stack<int> st;
    comps.clear();
    function<void(int, int, int&)> dfs = [&](int u, int p, int &t) {
      dfn[u] = low[u] = ++t;
      st.push(u);
      int cntp = 0;
      for(auto [v, idx] : g[u]) {
        cntp += v == p;
        if(!dfn[v])	{
          dfs(v, u, t);
          low[u] = min(low[u], low[v]);
          if(with_bridge && low[v] > dfn[u]) {
            bridge.push_back(make_pair(make_pair(min(u,v), max(u,v)), idx));
            comps.push_back({});
            for(int w = -1; w != v; )
              comps.back().push_back(w = st.top()), st.pop();
          }
          if(!with_bridge && low[v] >= dfn[u]) {
            art[u] = (dfn[u] > 1 || dfn[v] > 2);
            comps.push_back({u});
            for(int w = -1; w != v; )
              comps.back().push_back(w = st.top()), st.pop();
          }
        }
        else if(v != p || cntp > 1) low[u] = min(low[u], dfn[v]);
      }
      if(p == -1 && ( with_bridge || g[u].size() == 0 )) {
        comps.push_back({});
        for(int w = -1; w != u; )
          comps.back().push_back(w = st.top()), st.pop();
      }
    };
    for(int u = 1, t; u <= n; ++u)
      if(!dfn[u]) dfs(u, -1, t = 0);
  }
  vector<vector<pii>> build_bridge_tree() {
    tarjan(true);
    vector<vector<pii>> tree(comps.size());
    for(int i = 0; i < comps.size(); ++i)
      for(int u : comps[i]) id[u] = i;
    for(auto &b : bridge)
      add_edge(tree, id[b.ff.ff], id[b.ff.ss], b.ss);
    return tree;
  }
};

void dfs (int u, int p) { 
  st[u][0] = p;
  visi[u] = 1;
  tin[u] = cnt++;
  for (auto &v : bridge_tree[u]) { 
    if (v.ff == p) continue;
    dfs(v.ff, u);
  }
  tout[u] = cnt - 1;
}

bool anc (int u, int v) { 
  if (tin[u] <= tin[v] && tout[v] <= tout[u]) return true;
  return false;
}

int lca (int u, int v) { 
  if (anc(u, v)) return u;

  for (int i = 19; i >= 0; --i) { 
    if (!anc(st[u][i], v))
      u = st[u][i];
  }
  return st[u][0];
}

void solve (int u, int p, int id) { 
  visi[u] = 1;
  for (auto &v : bridge_tree[u]) { 
    if (v.ff == p) continue;
    solve (v.ff, u, v.ss);
    up[u] += up[v.ff];
    down[u] += down[v.ff];
  }

  assert(up[u] == 0 || down[u] == 0);

  if (up[u]) {
    if (u == edges[id].ff) ans[id] = 'R';
    else ans[id] = 'L';
  }
  if (down[u]) {
    if (p == edges[id].ff) ans[id] = 'R';
    else ans[id] = 'L';
  }
}

int main () {
        
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif

  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int n, m, p; 
  cin >> n >> m;

  

  tarjan_tree tj(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    ans[i] = 'B';
    edges[i] = {a, b};
    if (a == b) {
      continue;
    }
    else {
      tj.add_edge(a, b, i);
    }
  }

  bridge_tree = tj.build_bridge_tree();


  int nn = bridge_tree.size();

  for (int i = 0; i < nn; ++i)
    if (!visi[i]) dfs(i,i);

  for (int i = 1; i < 20; ++i) { 
    for (int j = 0; j < nn; ++j) { 
      st[j][i] = st[st[j][i-1]][i-1];
    }
  }

  cin >> p;

  for (int i = 0; i < p; ++i) { 
    int u, v; cin >> u >> v;
    u = tj.id[u], v = tj.id[v];

    int lc = lca(u, v);

    //cout << u << " " << v << " " << lc << '\n';

    up[u]++;
    up[lc]--;
    down[v]++;
    down[lc]--;
  }

  for (int i = 0; i < m; ++i) {
    edges[i].ff = tj.id[edges[i].ff];
    edges[i].ss = tj.id[edges[i].ss];
  }

  memset(visi, 0, sizeof visi);
  for (int i = 0; i < nn; ++i) {
    if (!visi[i]) solve(i,i,-1);
  }

  for (int i = 0; i < m; ++i) {
    cout << ans[i];
  }
  cout << '\n';

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In member function 'std::vector<std::vector<std::pair<int, int> > > tarjan_tree::build_bridge_tree()':
oneway.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0; i < comps.size(); ++i)
      |                    ~~^~~~~~~~~~~~~~

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