제출 #1114770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114770		VinhLuu	Tourism (JOI23_tourism)	C++17	100 / 100	573 ms	81992 KiB

tourism

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 5;

int n, m, q, L[N], R[N], c[N];
vector<int> p[N];

namespace AC{
  struct BIT{
    int bit[N];
    void update(int x,int val){
      if(!x) return;
      for(int i = x; i <= m; i += i & -i) bit[i] += val;
    }
    int get(int x){
      int ret = 0;
      for(int i = x; i; i -= i & -i) ret += bit[i];
      return ret;
    }
  } tree;

  int in[N], en[N], demin, be[N], head[N], scc = 1, pa[N], f[22][N], sub[N], d[N];

  void cal(int u,int v){
    sub[u] = 1;
    for(auto j : p[u]) if(j != v){
      pa[j] = u;
      d[j] = d[u] + 1;
      cal(j, u);
      sub[u] += sub[j];
    }
  }

  void hld(int u,int v){
    in[u] = ++demin;
    if(u == 1) for(int i = 0; i <= 18; i ++) f[i][u] = u;
    else{
      f[0][u] = v;
      for(int i= 1; i <= 18; i ++) f[i][u] = f[i - 1][f[i - 1][u]];
    }

    if(!head[scc]) head[scc] = u;
    be[u] = scc;

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

    if(mx) hld(mx, u);

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

    en[u] = demin;

  }

  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 = 18; i >= 0; i --) if(kt(f[i][u], v)) lca = f[i][u];
    else u = f[i][u];
    return lca;
  }

  struct interval{
    int nxt[N], wt[N];
    set<int> pot;
    void build(){
      nxt[1] = n + 1;
      pot.insert(1);
      wt[1] = 0;
    }

    void change(int l,int r,int val){
      if(l > r) return;
      auto _left = pot.upper_bound(l);
      _left--;
      auto _right = pot.upper_bound(r);
      _right--;

      int pl = (*_left);
      int pr = (*_right);

      if(pl == pr){
        tree.update(wt[pl], - nxt[pl] + pl);
        int ending = nxt[pl];
        if(pl < l){
          nxt[pl] = l;
          tree.update(wt[pl], l - pl);
        }
        if(r < ending - 1){
          pot.insert(r + 1);
          wt[r + 1] = wt[pl];
          nxt[r + 1] = ending;
          tree.update(wt[r + 1], ending - r - 1);
        }
        pot.insert(l);
        nxt[l] = r + 1;
        wt[l] = val;
        tree.update(val, r - l + 1);
        return;
      }

      int nxt_left = nxt[pl];
      int nxt_right = nxt[pr];
      tree.update(wt[pl], - nxt_left + pl);
      tree.update(wt[pr], - nxt_right + pr);
      pot.erase(pr);

      if(pl < l){
        nxt[pl] = l;
        tree.update(wt[pl], l - pl);
      }

      if(r < nxt_right - 1){
        pot.insert(r + 1);
        wt[r + 1] = wt[pr];
        nxt[r + 1] = nxt_right;
        tree.update(wt[r + 1], nxt_right - r - 1);
      }

      int tmp = nxt_left;

      while(tmp < pr){
        pot.erase(tmp);
        tree.update(wt[tmp], - nxt[tmp] + tmp);
        tmp = nxt[tmp];
      }

      pot.insert(l);
      nxt[l] = r + 1;
      wt[l] = val;
      tree.update(val, r - l + 1);
    }
  } data;

  void add(int u,int id){
    while(true){
      if(be[u] == be[1]){
        data.change(in[1], in[u], id);
        return;
      }
      int x = head[be[u]];
      data.change(in[x], in[u], id);
      u = pa[x];
    }
  }

  int kq[N];
  vector<int> Q[N];

  int Max[22][N], Min[22][N], LG[N];

  int get_max(int l,int r){
    int k = LG[r - l + 1];
    if(in[Max[k][l]] > in[Max[k][r - (1 << k) + 1]]) return Max[k][l];
    return Max[k][r - (1 << k) + 1];
  }

  int get_min(int l,int r){
    int k = LG[r - l + 1];
    if(in[Min[k][l]] < in[Min[k][r - (1 << k) + 1]]) return Min[k][l];
    return Min[k][r - (1 << k) + 1];
  }

  void solve(){
    cal(1, 0);
    hld(1, 0);
    LG[1] = 0;
    for(int i = 2; i <= m; i ++) LG[i] = LG[i / 2] + 1;

    for(int i = m; i >= 1; i --){
      Max[0][i] = c[i];
      Min[0][i] = c[i];
      for(int j = 1; j <= 18 && i + (1 << j) - 1 <= m; j ++){
        if(in[Max[j - 1][i]] > in[Max[j - 1][i + (1 << (j - 1))]]) Max[j][i] = Max[j - 1][i];
        else Max[j][i] = Max[j - 1][i + (1 << (j - 1))];
        if(in[Min[j - 1][i]] < in[Min[j - 1][i + (1 << (j - 1))]]) Min[j][i] = Min[j - 1][i];
        else Min[j][i] = Min[j - 1][i + (1 << (j - 1))];
      }
    }

    for(int i = 1; i <= q; i ++){
      Q[R[i]].push_back(i);
    }

    data.build();

    for(int r = 1; r <= m; r ++){
      add(c[r], r);
      for(auto j : Q[r]){
        int mi = get_min(L[j], r);
        int mx = get_max(L[j], r);
        kq[j] = tree.get(m) - tree.get(L[j] - 1) - d[LCA(mx, mi)];
      }
    }
    for(int i = 1; i <= q; i ++) cout << kq[i] << "\n";
  }
}

namespace sub1{
  int in[N], en[N], demin, f[22][N], d[N];
  void pre(int u,int v){
    in[u] = ++demin;
    if(u == 1) for(int i = 0; i <= 15; i ++) f[i][u] = u;
    else{
      f[0][u] = v;
      for(int i = 1; i <= 15; i ++) f[i][u] = f[i - 1][f[i - 1][u]];
    }
    for(auto j : p[u]) if(j != v){
      d[j] = d[u] + 1;
      pre(j, u);
    }
    en[u] = demin;
  }
  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 kq = u;
    for(int i = 15; i >= 0; i --) if(kt(f[i][u], v)) kq = f[i][u];
    else u = f[i][u];
    return kq;
  }

  void solve(){
    pre(1, 0);
    for(int k = 1; k <= q; k ++){
      int l = L[k], r = R[k];
      int ans = 0;
      vector<int> st;

      int mi = 0, mx = 0;

      for(int j = l; j <= r; j ++){
        int i = c[j];
        if(!in[mi] || in[mi] > in[i]) mi = i;
        if(!in[mx] || in[mx] < in[i]) mx = i;
        st.push_back(in[c[j]]);
      }

      sort(all(st));

      for(int i = 1; i <= n; i ++){
        auto _left = lower_bound(all(st), in[i]) - st.begin();
        auto _right = upper_bound(all(st), en[i]) - st.begin() - 1;
        if(0 <= _left && _left <= _right && _right <= (int)st.size() - 1) ans++;
      }

      cout << ans - d[LCA(mx, mi)] << "\n";
    }
  }
}


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 >> m >> q;
  for(int i = 1; i < n; i ++){
    int x, y; cin >> x >> y;
    p[x].push_back(y);
    p[y].push_back(x);
  }

  for(int i = 1; i <= m; i ++) cin >> c[i];

  for(int i = 1; i <= q; i ++){
    cin >> L[i] >> R[i];
  }

  AC :: solve();
}

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

tourism.cpp: In function 'int main()':
tourism.cpp:274:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:275:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  275 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41