제출 #1069617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069617		duckindog	Inside information (BOI21_servers)	C++17	100 / 100	582 ms	118612 KiB

servers

#include <bits/stdc++.h>

using namespace std;

const int N = 120'000 + 10,
          MAX = 1'000'000;
int n, k;
vector<pair<int, int>> ad[N];
vector<tuple<int, int, int>> Q;

namespace group1 { 
  int st[N], ed[N], it;
  int f[N][18], increase[N][18], decrease[N][18];
  void dfs(int u, int p = -1) { 
    st[u] = ++it;
  
    for (int i = 1; i <= 17; ++i) { 
      f[u][i] = f[f[u][i - 1]][i - 1];
  
      if (increase[u][i - 1] != -1 && increase[f[u][i - 1]][i - 1] != -1) { 
        if (increase[u][i - 1] < increase[f[u][i - 1]][0]) 
          increase[u][i] = increase[f[u][i - 1]][i - 1];
      }
      if (decrease[u][i - 1] != -1 && decrease[f[u][i - 1]][i - 1] != -1) { 
        if (decrease[u][i - 1] > decrease[f[u][i - 1]][0]) 
          decrease[u][i] = decrease[f[u][i - 1]][i - 1];
      }
    }
  
    for (const auto& [v, w] : ad[u]) { 
      if (v == p) continue;
      f[v][0] = u;
      increase[v][0] = decrease[v][0] = w;
      dfs(v, u);
    }
  
    ed[u] = it;
  }
  inline bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }

  void init() { 
    memset(increase, 63, sizeof increase);
    dfs(f[1][0] = 1); 
  }

  int get(int u, int v) { 
    int uwd = 0, dwd = MAX, ma = 0;
    for (int i = 17; i >= 0; --i) { 
      if (anc(f[u][i], v)) continue;
      if (uwd >= increase[u][0]) return MAX;
      uwd = increase[u][i];
      u = f[u][i];
    }
    if (!anc(u, v)) { 
      if (uwd >= increase[u][0]) return MAX;
      uwd = increase[u][0];
      u = f[u][0];
    } ma = uwd;
    
    for (int i = 17; i >= 0; --i) { 
      if (anc(f[v][i], u)) continue;
      if (dwd <= decrease[v][0]) return MAX;
      dwd = decrease[v][i];
      ma = max(ma, decrease[v][0]);
      v = f[v][i];
    }
    if (v != u) { 
      if (dwd <= decrease[v][0]) return MAX;
      dwd = decrease[v][0];
      ma = max(ma, decrease[v][0]);
      v = f[v][0];
    }
  
    return uwd < dwd ? ma : MAX;
  }
}

namespace group2 { 
  int sz[N];
  void dfs0(int u, int p = -1) { 
    for (const auto& [v, w] : ad[u]) { 
      if (v == p) continue;
      dfs0(v, u);
      sz[u] += sz[v] + 1;
    }
  }

  int st[N], ed[N], rvs[N], it;
  int head[N], par[N];
  int minimum[N];
  void hld(int u, int p = -1) { 
    st[u] = ++it; rvs[u] = it;
    if (!head[u]) head[u] = u;

    sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
      return sz[a.first] > sz[b.first];
    });

    int heavy = 0;
    for (const auto& [v, w] : ad[u]) { 
      if (v == p) continue;
      if (!heavy) heavy = head[v] = head[u], minimum[u] = w;
      par[v] = u;
      hld(v, u);
    }

    ed[u] = it;
  }
  
  struct IT { 
    vector<int> rrh;
    vector<int> f, lazy;
    inline void push(int s, int l, int r) { 
      int mid = (l + r) >> 1;
      f[s << 1] += (mid - l + 1) * lazy[s];   f[s << 1 | 1] += (r - mid) * lazy[s];
      lazy[s << 1] += lazy[s];                lazy[s << 1 | 1] += lazy[s];
      lazy[s] = 0;
    }
    void update(int s, int l, int r, int u, int v, int x) { 
      if (v < l || u > r) return;
      if (u <= l && r <= v) { 
        f[s] += (r - l + 1) * x;
        lazy[s] += x;
        return;
      }
      push(s, l, r);
      int mid = (l + r) >> 1;
      update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
      f[s] = f[s << 1] + f[s << 1 | 1];
    }
    int query(int s, int l, int r, int u, int v) { 
      if (v < l || u > r) return 0;
      if (u <= l && r <= v) return f[s];
      push(s, l, r);
      int mid = (l + r) >> 1;
      return query(s << 1, l, mid, u, v) + query(s << 1 | 1, mid + 1, r, u, v);
    }
    void upd(int l, int r, int x) { update(1, 1, rrh.size(), l, r, x); }
    int que(int l, int r) { return query(1, 1, rrh.size(), l, r); }

  } T[N], D, E;

  void init() { 
    dfs0(1); hld(par[1] = 1);
    D.rrh = vector<int>(n); 
    E.rrh = vector<int>(n);
    D.f = D.lazy = vector<int>(n + 10 << 2);
    E.f = E.lazy = vector<int>(n + 10 << 2);

    for (int u = 1; u <= n; ++u) { 
      for (const auto& [v, w] : ad[u]) 
        if (par[v] == u) T[u].rrh.push_back(w);
      sort(T[u].rrh.begin(), T[u].rrh.end());
      T[u].f = T[u].lazy = vector<int>(T[u].rrh.size() + 10 << 2);
    }
  }
  int cnt[N];
  void add(int u, int v, int time) { 
    if (par[u] == v) swap(u, v);

    int x = v;
    for (int i = 17; i >= 0; --i) { 
      int moment = group1::get(group1::f[x][i], v);
      if (moment <= time) x = group1::f[x][i];
    }

    while (head[v] != head[x]) { 
      int moment = group1::decrease[head[v]][0];
      E.upd(st[head[v]], st[v] - 1, 1);
      v = par[head[v]];
      E.upd(st[v], st[v], 1); cnt[v] += 1;
      D.upd(st[v], st[v], moment > minimum[v]);

      int it = upper_bound(T[v].rrh.begin(), T[v].rrh.end(), moment) - T[v].rrh.begin();
      T[v].upd(it, it, 1);
    } E.upd(st[x], st[v] - 1, 1);
  }

  int get(int u, int time) { 
    int uwd = 0, x = u;
    for (int i = 17; i >= 0; --i) { 
      if (group1::increase[x][i] > time || uwd > group1::increase[x][0]) continue;
      uwd = group1::increase[x][i];
      x = group1::f[x][i];
    } 

    int ret = E.que(st[u], st[u]);
    while (head[u] != head[x]) { 
      ret += st[u] - st[head[u]] + 1;
      ret += D.que(st[head[u]], st[u] - 1);

      int moment = group1::increase[head[u]][0];
      u = par[head[u]];
      if (moment < minimum[u]) ret += E.que(st[u], st[u]) - cnt[u];

      int it = upper_bound(T[u].rrh.begin(), T[u].rrh.end(), moment) - T[u].rrh.begin() + 1;
      ret += T[u].que(it, T[u].rrh.size());
    } ret += D.que(st[x], st[u] - 1) + st[u] - st[x] + 1;

    return ret;
  }
};

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k;
  for (int i = 1; i < n + k; ++i) { 
    char type; cin >> type;
    if (type == 'S') { 
      int a, b; cin >> a >> b;
      ad[a].push_back({b, i});
      ad[b].push_back({a, i});
      Q.emplace_back(0, a, b);
    }

    if (type == 'Q') { 
      int a, d; cin >> a >> d;
      Q.emplace_back(1, a, d);
    }

    if (type == 'C') { 
      int d; cin >> d;
      Q.emplace_back(2, 0, d);
    }
  }

  group1::init(); group2::init();

  for (int i = 1; i < n + k; ++i) { 
    const auto& [type, a, b] = Q[i - 1];

    if (!type) group2::add(a, b, i);
    else if (type == 1) cout << (group1::get(b, a) <= i ? "yes" : "no") << "\n";
    else cout << group2::get(b, i) << "\n";
  }
}

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

servers.cpp: In function 'void group2::init()':
servers.cpp:147:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  147 |     D.f = D.lazy = vector<int>(n + 10 << 2);
      |                                ~~^~~~
servers.cpp:148:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  148 |     E.f = E.lazy = vector<int>(n + 10 << 2);
      |                                ~~^~~~
servers.cpp:154:56: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  154 |       T[u].f = T[u].lazy = vector<int>(T[u].rrh.size() + 10 << 2);
      |                                        ~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5