Submission #927913

#	Time	Username	Problem	Language	Result	Execution time	Memory
927913		TAhmed33	One-Way Streets (CEOI17_oneway)	C++98	100 / 100	841 ms	79044 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 1e5 + 25;
struct SegmentTree {
  int lazy[2 * MAXN];
  int tree[2 * MAXN];
  void prop(int l, int r, int node) {
    if (lazy[node] == -1) return;
    if (l == r) {
      tree[node] = lazy[node];
    } else {
      lazy[tl] = lazy[tr] = lazy[node];
    }
    lazy[node] = -1;
  }
  void update(int l, int r, int a, int b, int c, int node) {
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
      lazy[node] = c;
      prop(l, r, node);
      return;
    }
    update(l, mid, a, b, c, tl);
    update(mid + 1, r, a, b, c, tr);
  }
  int get(int l, int r, int a, int node) {
    prop(l, r, node);
    if (l == r) {
      return tree[node];
    }
    if (a <= mid) return get(l, mid, a, tl);
    return get(mid + 1, r, a, tr);
  }
};
SegmentTree cur;
set < pair < int, int >> bridges;
vector < int > adj1[MAXN];
int in [MAXN], low[MAXN];
bool vis[MAXN];
int t = 0;
vector < pair < int, int >> edges;
map < pair < int, int > , int > ans;
map < pair < int, int > , int > cnt;
void dfs(int pos, int par) {
  vis[pos] = 1;
  in [pos] = low[pos] = ++t;
  for (auto j: adj1[pos]) {
    if (j == par) continue;
    if (vis[j]) {
      low[pos] = min(low[pos], in [j]);
      continue;
    }
    dfs(j, pos);
    low[pos] = min(low[pos], low[j]);
    if (cnt[{
        j,
        pos
      }] == 1 && low[j] > in [pos]) {
      bridges.insert({
        pos,
        j
      });
    }
  }
}
struct DSU {
  int sze[MAXN], par[MAXN];
  void init() {
    for (int i = 1; i < MAXN; i++) {
      sze[i] = 1;
      par[i] = i;
    }
  }
  int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
  }
  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sze[x] > sze[y]) swap(x, y);
    sze[y] += sze[x];
    par[x] = y;
  }
};
DSU comps;
vector < pair < int, int >> adj[MAXN];
int p[MAXN];
int sze[MAXN];
int dep[MAXN];
void dfs2(int pos, int par) {
  p[pos] = par;
  sze[pos] = 1;
  vis[pos] = 1;
  for (int i = 0; i < (int) adj[pos].size(); i++) {
    if (adj[pos][i].first == par) {
      adj[pos].erase(adj[pos].begin() + i);
      break;
    }
  }
  for (auto & j: adj[pos]) {
    dep[j.first] = 1 + dep[pos];
    dfs2(j.first, pos);
    sze[pos] += sze[j.first];
    if (sze[j.first] > sze[adj[pos][0].first]) {
      swap(j, adj[pos][0]);
    }
  }
}
int in2[MAXN], out2[MAXN], nxt[MAXN];
void dfs3(int pos) {
  in2[pos] = ++t;
  for (auto j: adj[pos]) {
    nxt[j.first] = (j.first == adj[pos][0].first ? nxt[pos] : j.first);
    dfs3(j.first);
  }
  out2[pos] = t;
}
int uy;
map < int, int > xx, xx2;
int dp[32][MAXN];
int jump(int a, int b) {
  for (int i = 23; i >= 0; i--) {
    if ((b & (1 << i)) && dp[i][a]) a = dp[i][a];
    else if (b & (1 << i)) return 0;
  }
  return a;
}
int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  int u = dep[a] - dep[b];
  a = jump(a, u);
  if (a == b) return a;
  for (int i = 23; i >= 0; i--) {
    int x = dp[i][a], y = dp[i][b];
    if (x && y && x != y) a = x, b = y;
  }
  return jump(a, 1);
}
void upd (int a, int b) {
  while (a) {
    if (in2[nxt[a]] <= in2[b]) {
      if (in2[b] < in2[a]) cur.update(1, uy, in2[b] + 1, in2[a], 1, 1);
      return;
    }
    cur.update(1, uy, in2[nxt[a]], in2[a], 1, 1);
    a = p[nxt[a]];
  }
}
void dow (int a, int b) {
  while (a) {
    if (in2[nxt[a]] <= in2[b]) {
      if (in2[b] < in2[a]) cur.update(1, uy, in2[b] + 1, in2[a], 2, 1);
      return;
    }
    cur.update(1, uy, in2[nxt[a]], in2[a], 2, 1);
    a = p[nxt[a]];
  }
}
void dfs5 (int pos, int par) {
  vis[pos] = 1;
  for (auto j : adj[pos]) {
    if (j.first != par) {
      dfs5(j.first, pos);
    }
    int x = cur.get(1, uy, in2[j.first], 1);
    pair <int, int> tt = edges[j.second];
    if (x == 0) {
      ans[tt] = 0;
      continue;
    }
    if (pos == xx[comps.find(tt.second)]) {
      x = 3 - x;
    }
    ans[tt] = x;
  }
}
int main() {
  memset(cur.lazy, -1, sizeof(cur.lazy));
  int n, m;
  cin >> n >> m;
  comps.init();
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    cnt[{a, b}]++;
    cnt[{b, a}]++;
    edges.push_back({a, b});
    if (a == b) {
      ans[{a, b}] = ans[{b, a}] = 0;
      continue;
    }
    if (cnt[{a, b}] > 1) {
      ans[{a, b}] = ans[{b, a}] = 0;
      continue;
    }
    adj1[a].push_back(b);
    adj1[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, 0);
    }
  }
  for (auto[a, b]: edges) {
    if (!bridges.count({b, a}) && !bridges.count({a, b})) {
      comps.merge(a, b);
      ans[{a, b}] = ans[{b, a}] = 0;
    }
  }
  int uu = 0;
  set < int > pp;
  for (int i = 1; i <= n; i++) pp.insert(comps.find(i));
  uy = pp.size();
  for (auto i: pp) {
    xx[i] = xx.size() + 1;
  }
  for (auto i: xx) {
    xx2[i.second] = i.first;
  }
  for (auto[a, b]: edges) {
    if (bridges.count({b, a}) || bridges.count({a, b})) {
      adj[xx[comps.find(a)]].push_back({xx[comps.find(b)], uu});
      adj[xx[comps.find(b)]].push_back({xx[comps.find(a)], uu});
    }
    uu++;
  }
  memset(vis, 0, sizeof(vis));
  t = 0;
  for (int i = 1; i <= uy; i++) {
    if (!vis[i]) {
      dfs2(i, 0);
      nxt[i] = i;
      dfs3(i);
    }
  }
  for (int i = 1; i <= uy; i++) dp[0][i] = p[i];
  for (int i = 1; i <= 23; i++) {
    for (int j = 1; j <= uy; j++) {
      dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
  }
 /* for (int i = 1; i <= uy; i++) {
    cout << nxt[i] << " " << p[i] << " " << in2[i] << endl;
  }
  cout << "__________\n";*/
  int q;
  cin >> q;
  while (q--) {
    int a, b;
    cin >> a >> b;
    if (comps.find(a) == comps.find(b)) continue;
    a = xx[comps.find(a)];
    b = xx[comps.find(b)];
    int x = lca(a, b);
    //cout << a << " " << b << " " << x << endl;
    if (x != a) upd(a, x);
    if (x != b) dow(b, x);
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= uy; i++) {
    if (!vis[i]) {
      dfs5(i, 0);
    }
  }
  for (auto i : edges) {
    int z = ans[{i.first, i.second}];
    if (z == 0) cout << "B";
    else if (z == 2) cout << "R";
    else cout << "L";
  }
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:208:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |   for (auto[a, b]: edges) {
      |            ^
oneway.cpp:224:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  224 |   for (auto[a, b]: edges) {
      |            ^

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