Submission #1278103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278103		sasde	Tourism (JOI23_tourism)	C++20	100 / 100	1066 ms	50144 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define se second
#define fi first
#define emb emplace_back
#define look_memory cerr<<'\n'<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time   cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=3e5+5,inf=1e9,lim=2e5;
int node,query,m,c[N];
ii b[N];
namespace sub456{
struct HLD {
  int n, curpos, curc;
  int bit[N];
  vector<int> h,sl, up, curhead, curid, pos, posend, arr;
  vector<vector<int>> edge;

  HLD() : curpos(0), curc(0) {};
  HLD(int _n) : n(_n),  sl(n + 5), h(n + 5), up(n + 5),
  curhead(n + 5), curid(n + 5), pos(n + 5), posend(n+5), arr(n + 5), edge(n + 5) {
    curpos = curc = 0;
  };
  void addedge(int u, int v) {
    edge[u].emplace_back(v);
    edge[v].emplace_back(u);
  }
  void update(int idx,int val){
//      cout <<idx<<" "<<val<<'\n';
    while(idx<=N-1){
        bit[idx]+=val;
        idx+=idx&(-idx);
    }
  }
  int get(int idx){
    int res=0;
    while(idx>0){
        res+=bit[idx];
        idx-=idx&(-idx);
    }
    return res;
  }
  int getrange(int l,int r){
//      cout <<get(r)<<" "<<get(l-1)<<'\n';
    return get(r)-get(l-1);

  }
  void dfs(int u, int cha) {
    sl[u] = 1;
    for (int v : edge[u]) {
      if (v == cha) continue;
      h[v] = h[u] + 1;
      up[v] = u;
      dfs(v, u);
      sl[u] += sl[v];
    }
  }

  void hld(int u, int cha) {
    if (!curhead[curc]) curhead[curc] = u;
    curid[u] = curc;
    pos[u] = ++curpos;
    arr[curpos] = u;
    int nxt = 0;
    for (int v : edge[u]) {
      if (v != cha && sl[v] > sl[nxt]) nxt = v;
    }
    if (nxt) hld(nxt, u);
    for (int v : edge[u]) {
      if (v != cha && v != nxt) {
        ++curc;
        hld(v, u);
      }
    }
    posend[u]=curpos;
  }
  void build(int goc){
    dfs(goc,-1);
    hld(goc,-1);
  }
  set<array<int,3>>s;
  void doi(int l,int r,int x){
      while(true){
            auto it=s.lower_bound({l,-inf,-inf});
            if(it==s.end())break;
            array<int,3>x=*it;
            int u=x[1];
            int v=x[0];
            int val=x[2];
            if(r<u||l>v)break;
            s.erase(it);
            int len=min(r,v)-max(l,u)+1;
//                cout <<u<<" "<<v<<" "<<val<<" "<<len<<'\n';
            update(val+1,-len);
            if(u<l)s.insert({l-1,u,val});
            if(r<v)s.insert({v,r+1,val});
      }

      update(x+1,r-l+1);
      s.insert({r,l,x});
  }
  void change(int u,int v,int val){
    for(;curid[u]!=curid[v];v=up[curhead[curid[v]]]){
      if(h[curhead[curid[u]]]>h[curhead[curid[v]]])swap(u,v);
              doi(pos[curhead[curid[v]]],pos[v],val);
    }
    if(h[u]>h[v])swap(u,v);
        doi(pos[u],pos[v],val);
  }
};
    vector<ii>req[N];
    int ans[N];
    void solve(){
        HLD hld(node);
        for(int i=1;i<node;++i){
            hld.addedge(b[i].fi,b[i].se);
        }
        for(int i=1;i<=query;++i){
            int l,r;
            cin >> l >>r;
            ans[i]=1;
            req[r].emb(l,i);
        }
        hld.build(1);
        for(int i=1;i<=m;++i){
            if(i>1){
                hld.change(c[i-1],c[i],i-1);
            }
            hld.change(c[i],c[i],i);
            for(auto x:req[i])ans[x.se]=hld.getrange(x.fi+1,m+1);
        }
        for(int i=1;i<=query;++i)cout << ans[i]<<"\n";
        for(int i=1;i<=query;++i)cerr << ans[i]<<"\n";

    }

}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    #define task "aws"
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    cin >> node>>m >> query;
    for(int i=1;i<node;++i){
        int u,v;
        cin >> u >> v;
        b[i]={u,v};
    }
    for(int i=1;i<=m;++i)cin >> c[i];
    sub456::solve();

}

Compilation message (stderr)

tourism.cpp:141:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  141 | main()
      | ^~~~
tourism.cpp: In function 'int main()':
tourism.cpp:148:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:149:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |       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