제출 #1082116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082116		VinhLuu	Inside information (BOI21_servers)	C++17	5 / 100	118 ms	47444 KiB

servers

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 2e9;

struct IT {
  int st[N << 2], lz[N << 2];
  void dolz(int i,int l,int r){
    if(!lz[i]) return;
    int x = lz[i], mid = (l + r) / 2; lz[i] = 0;
    st[i << 1] += x * (mid - l + 1), st[i << 1|1] += x * (r - mid);
    lz[i << 1] += x, lz[i << 1|1] += x;
  }

  void update(int i,int l,int r,int u,int v,int x){
    if(l > r || r < u || v < l) return;
    if(u <= l && r <= v){
      st[i] += x * (r - l + 1);
      lz[i] += x;
      return;
    }
    dolz(i, l, r);
    int mid = (l + r) / 2;
    update(i << 1, l, mid, u, v, x);
    update(i << 1|1, mid + 1, r, u, v, x);
    st[i] = st[i << 1] + st[i << 1|1];
  }

  int get(int i,int l,int r,int u,int v){
    if(l > r || r < u || v < l) return 0;
    if(u <= l && r <= v) return st[i];
    dolz(i, l, r);
    int mid = (l + r) / 2;
    return get(i << 1, l, mid, u, v) + get(i << 1|1, mid + 1, r, u, v);
  }
} f[2];

struct DSU{
  int par[N];

  void re(int n){
    for(int i = 1; i <= n; i ++) par[i] = i;
  }
  int fin(int u){
    return par[u] == u ? u : par[u] = fin(par[u]);
  }
  void dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return;
    par[u] = v;
  }
} g[2];

int n, q, T[N], X[N], Y[N], in[N], demin, en[N], head[N], pa[N], dp[N][22], d[N], be[N], h[N], key[2][N], tn[N];
vector<pii> p[N];

bool kt(int u,int v){
  return in[u] <= in[v] && in[v] <= en[u];
}

int LCA(int u,int v){
  if(kt(u, v)) return u;
  int lca = u;
  for(int i = 20; i >= 0; i --) if(kt(dp[u][i], v)) lca = dp[u][i]; else u = dp[u][i];
  return lca;
}

void dfs(int u,int v){

  d[u] = 1;
  for(auto [j, w] : p[u]) if(j != v){
    dfs(j, u);
    d[u] += d[j];
    pa[j] = u;
    h[j] = w;
  }

}

int scc = 1;

vector<int> vr[N], b[N];

void hld(int u,int v){
  in[u] = ++demin;
  if(!head[scc]) head[scc] = u;
  be[u] = scc;
  tn[demin] = u;
  if(!v){
      for(int i = 0; i <= 20; i ++) dp[u][i] = u;
  }else{
    dp[u][0] = v;
    for(int i = 1; i <= 20; i ++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
  }

  int mx = 0, val = 0;
  for(auto [j, w] : p[u]) if(j != v && d[j] > d[mx]) val = w, mx = j;

  key[0][u] = mx, key[1][u] = val;

  if(mx) hld(mx, u);

  for(auto [j, w] : p[u]) if(j != v && j != mx){
    scc++;
    vr[u].pb(w);
    hld(j, u);
  }

  sort(all(vr[u]));
  for(auto j : vr[u]) b[u].pb(0);

  en[u] = demin;
}

void up(int u,int tmp){
  if(h[pa[u]] <= tmp){
    if(pa[u] == 1){
      g[0].dsu(u, pa[u]);
      g[1].dsu(u, pa[u]);
    }else{
      if(h[pa[u]] > h[u]) g[0].dsu(u, pa[u]);
      else g[1].dsu(u, pa[u]);
    }
  }
  for(auto [j, w] : p[u]) if(j != pa[u]){
    if(w > h[u] && w <= tmp) g[1].dsu(j, u);
    if(w < h[u] && w <= tmp) g[0].dsu(j, u);
  }

  int v = g[1].fin(u), val = f[0].get(1, 1, n, in[u], in[u]);
  if(v != 1 && key[1][pa[v]] != h[v]){
    if(key[1][pa[v]] < h[v]) f[1].update(1, 1, n, in[pa[v]], in[pa[v]], val);
    int dr = lower_bound(all(vr[pa[v]]), h[v]) - vr[pa[v]].begin();
    b[pa[v]][dr] += val; // add
  }
  if(u == v) return;
  if(key[0][pa[u]] != u){
    int dr = lower_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin();
    b[pa[u]][dr] += val; // add
    if(key[1][pa[u]] < h[u]) f[1].update(1, 1, n, in[pa[u]], in[pa[u]], val);
  }
  u = pa[u];
  while(true){
    if(be[u] == be[v]){
      f[0].update(1, 1, n, in[v], in[u], val);
      return;
    }
    int j = pa[head[be[u]]];
    if(h[head[be[u]]] > key[1][tn[in[j]]]) f[1].update(1, 1, n, in[j], in[j], val);
    int dr = lower_bound(all(vr[j]), h[head[be[u]]]) - vr[j].begin();
    b[j][dr] += val; // add
    f[0].update(1, 1, n, in[head[be[u]]], in[u], val);
    u = j;
  }
}

int lc(int u,int v){
  int kq = u;
  if(u == v) return kq;
  for(int i = 20; i >= 0; i --) if(v != dp[u][i] && kt(v, dp[u][i])){
    kq = dp[u][i];
    u = dp[u][i];
  }
  return kq;
}

int query(int u,int v,int tmp){
  int lca = LCA(u, v);
  int fu = g[0].fin(u), fv = g[1].fin(v);
  if(h[fu] <= tmp) fu = pa[fu];
  if(h[fv] <= tmp) fv = pa[fv];
  if(kt(fu, lca) && kt(fv, lca)){
    fu = lc(u, lca), fv = lc(v, lca);
    if(fu == lca || fv == lca || h[fu] < h[fv]) return 1;
  }
  return 0;
}

int solve(int u,int tmp){
  int ans = 1;
  for(int i = 0; i < vr[u].size(); i ++) ans += b[u][i];
  if(h[key[0][u]] <= tmp && key[0][u]) ans += f[0].get(1, 1, n, in[key[0][u]], in[key[0][u]]);
  if(u == 1) return ans;

  int v = g[0].fin(u); if(h[v] <= tmp) v = pa[v];
  if(u == v) return ans;
  if(key[0][pa[u]] != u){
    int dr = upper_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin();
    for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
    ans++;
    if(h[key[0][pa[u]]] <= tmp && key[1][pa[u]] > h[u]) ans += f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]);

  }else{
    ans += f[1].get(1, 1, n, in[pa[u]], in[pa[u]]);
  }
  u = pa[u];
  while(true){
    if(be[u] == be[v]){
      if(u == v) return ans;
      ans += f[1].get(1, 1, n, in[v], in[u] - 1);
      return ans;
    }
    int j = pa[head[be[u]]];
//    cerr << j << " t\n";
    int k = head[be[u]];
    int pos = upper_bound(all(vr[j]), h[k]) - vr[j].begin();
    for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
    ans += f[1].get(1, 1, n, in[k], in[u] - 1);
    ans++;
    if(h[key[0][j]] <= tmp && key[1][j] > h[k]) ans += f[0].get(1, 1, n, in[key[0][j]], in[key[0][j]]);
    u = j;
  }
  return ans;
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> q;
  q = n + q - 1;
  g[1].re(n), g[0].re(n);
  for(int i = 1; i <= q; i ++){
    char c; cin >> c;
    if(c == 'S'){
      cin >> X[i] >> Y[i];
      T[i] = 0,
      p[X[i]].pb({Y[i], i});
      p[Y[i]].pb({X[i], i});
    }else if(c == 'Q'){
      T[i] = 1;
      cin >> X[i] >> Y[i];
    }else{
      T[i] = 2;
      cin >> X[i];
    }
  }

  pa[1] = 1;
  h[1] = 0;
  dfs(1, 0);
  hld(1, 0);

  for(int i = 1; i <= n; i ++) f[0].update(1, 1, n, in[i], in[i], 1), f[1].update(1, 1, n, in[i], in[i], 1);

  for(int i = 1; i <= q; i ++){
    if(T[i] == 0){
      if(in[X[i]] < in[Y[i]]) swap(X[i], Y[i]);
      up(X[i], i);
    }else if(T[i] == 1){
      int x = X[i], y = Y[i];
      if(in[x] > in[y]) swap(x, y);
      if(pa[y] == x){
        if(h[y] <= i) cout << "yes\n";
        else cout << "no\n";
        continue;
      }
      cout << (query(Y[i], X[i], i) == 1 ? "yes\n" : "no\n");
    }else {
      cout << solve(X[i], i) << "\n";
    }
  }
}

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

servers.cpp: In function 'void hld(int, int)':
servers.cpp:121:12: warning: unused variable 'j' [-Wunused-variable]
  121 |   for(auto j : vr[u]) b[u].pb(0);
      |            ^
servers.cpp: In function 'int solve(int, int)':
servers.cpp:192:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |   for(int i = 0; i < vr[u].size(); i ++) ans += b[u][i];
      |                  ~~^~~~~~~~~~~~~~
servers.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |     for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
      |                     ~~^~~~~~~~~~~~~~~~~~
servers.cpp:218:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
      |                      ~~^~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:231:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:232:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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