Submission #617215

#	Time	Username	Problem	Language	Result	Execution time	Memory
617215		WLZ	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	468 KiB

oneway

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

/** 1-indexed LCA class */
class least_common_ancestor {
  private:
    int n, max_log, dfs_cnt = 1;
    vector< vector< pair<int, int> > > g;
    vector< vector<int> > up;
    vector<int> d, dfs_in, dfs_out;

    void dfs(int u, int p) {
      dfs_in[u] = dfs_cnt++;
      up[u][0] = p;
      for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
      for (auto &v : g[u]) {
        if (v.first == u) continue;
        d[v.first] = d[u] + v.second;
        dfs(v.first, u);
      }
      dfs_out[u] = dfs_cnt;
    }

    void init() {
      n = (int) g.size() - 1;
      max_log = ceil(log2(n + 1));
      up.assign(n + 1, vector<int>(max_log + 1));
      d.assign(n + 1, 0);
      dfs_in.resize(n + 1);
      dfs_out.resize(n + 1);
      for (int i = 1; i <= n; i++) if (dfs_in[i] == 0) dfs(i, i);
    }
  public:
    /** Assumes g is an undirected tree. Can be directed if edges point away from vertex the root */
    least_common_ancestor(const vector< vector< pair<int, int> > > &_g) : g(_g) {
      init();
    }

    /** Assigns weight 1 to all edges in an unweighted tree */
    least_common_ancestor(const vector< vector<int> > &_g) {
      g.assign((int) _g.size(), vector< pair<int, int> >());
      for (int i = 0; i < (int) _g.size(); i++) {
        for (auto &x : _g[i]) g[i].emplace_back(x, 1);
      }
      init();
    }

    bool is_anc(int u, int v) {
      return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
    }

    int query(int u, int v) {
      if (is_anc(u, v)) return u;
      if (is_anc(v, u)) return v;
      for (int i = max_log; i >= 0; i--) {
        if (!is_anc(up[u][i], v)) u = up[u][i];
      }
      return up[u][0];
    }

    int depth(int u) {
      return d[u];
    }

    int dist(int u, int v) {
      return d[u] + d[v] - 2 * d[query(u, v)];
    }

    int preorder(int u) {
      return dfs_in[u];
    }

    int postorder(int u) {
      return dfs_out[u];
    }
};

vector< vector< pair<int, int> > > g, back, dfs_tree;
vector<bool> was, used;
vector< pair<int, int> > edges, p;
vector<int> up, down, over;
string ans;

void dfs(int u) {
  was[u] = true;
  for (auto &v : g[u]) {
    if (!was[v.first]) {
      p[v.first] = {u, v.second};
      dfs(v.first);
    } else if (v.first != p[u].first && !used[v.second]) {
      back[u].push_back(v);
      back[v.first].push_back({-u, v.second});
    }
    used[v.second] = true;
  }  
}

void dfs_2(int u) {
  for (auto &v : dfs_tree[u]) {
    dfs_2(v.first);
    down[u] += down[v.first];
    up[u] += up[v.first];
    over[u] += over[v.first];
  }
  for (auto &v : back[u]) {
    if (v.first < 0) over[u]--;
    else over[u]++;
  }
  if (over[u] == 0) {
    //assert(down[u] == 0 || up[u] == 0);
    if (down[u] > 0) {
      if (edges[p[u].second].second == u) ans[p[u].second] = 'R';
      else ans[p[u].second] = 'L';
    } else {
      if (edges[p[u].second].first == u) ans[p[u].second] = 'R';
      else ans[p[u].second] = 'L';
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  g.resize(n + 1);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    edges.push_back({u, v});
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  was.assign(n + 1, false);
  p.assign(n + 1, {-1, -1});
  back.resize(n + 1);
  used.assign(m, false);
  for (int i = 1; i <= n; i++) if (!was[i]) dfs(i);
  dfs_tree.resize(n + 1);
  for (int i = 2; i <= n; i++) if (p[i].first != -1) dfs_tree[p[i].first].push_back({i, p[i].second});
  least_common_ancestor lca(dfs_tree);
  up.assign(n + 1, 0); down.assign(n + 1, 0);
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    up[x]++; down[y]++;
    int tmp = lca.query(x, y);
    up[tmp]--; down[tmp]--;
  }
  ans = string(m, 'B');
  over.assign(n + 1, 0);
  dfs_2(1);
  for (int i = 0; i < m; i++) cout << ans[i];
  cout << '\n';
  return 0;
}

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