oj.uz

Submission #924662

# Submission time Handle Problem Language Result Execution time Memory
924662 2024-02-09T11:35:55 Z ttamx Tourism (JOI23_tourism) C++14
0 / 100
 103 ms 85556 KB 
#include<bits/stdc++.h>
#include<queue>

using namespace std;

const int N=1e5+5;
const int M=3e5+5;
const int LG=20;

int n,m,q;
int c[N];
vector<int> adj[N];
int sz[N],hv[N],hd[N],pa[N],lv[N],tin[N],tout[N],pos[N];
int timer;
vector<pair<int,int>> qr[N],chain[N];
int ans[N];

struct Fenwick{
    int t[N];
    void update(int i,int v){
        for(;i<N;i+=i&-i)t[i]+=v;
    }
    int query(int i){
        int res=0;
        for(;i;i-=i&-i)res+=t[i];
        return res;
    }
}f;

template<class T,class cmp>
struct RMQ{
    T t[LG][M];
    T get_min(T a,T b){
        return cmp()(a,b)?a:b;
    }
    void build(){
        for(int i=0;i<LG-1;i++){
            for(int j=1;j+(2<<i)-1<M;j++){
                t[i+1][j]=get_min(t[i][j],t[i][j+(1<<i)]);
            }
        }
    }
    T query(int l,int r){
        int k=31-__builtin_clz(r-l+1);
        return get_min(t[k][l],t[k][r-(1<<k)+1]);
    }
};

RMQ<int,less<int>> rtin,rdep;
RMQ<int,greater<int>> rtout;

void dfs(int u,int p=0){
    tin[u]=++timer;
    pos[timer]=u;
    pa[u]=p;
    sz[u]=1;
    for(auto v:adj[u])if(v!=p){
        lv[v]=lv[u]+1;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
        pos[++timer]=u;
    }
    tout[u]=timer;
}

void hld(int u,int p=0){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    for(int i=1;i<=m;i++)cin >> c[i];
    for(int i=1;i<=q;i++){
        int l,r;
        cin >> l >> r;
        qr[r].emplace_back(l,i);
    }
    dfs(1);
    hld(1);
    for(int i=1;i<=timer;i++)rdep.t[0][i]=lv[pos[i]];
    for(int i=1;i<=m;i++){
        rtin.t[0][i]=tin[c[i]];
        rtout.t[0][i]=tout[c[i]];
    }
    rdep.build();
    rtin.build();
    rtout.build();
    for(int r=1;r<=n;r++){
        for(int u=c[r];u;u=pa[u]){
            int h=hd[u];
            auto &ch=chain[h];
            while(!ch.empty()&&lv[ch.back().first]<=lv[u]){
                auto [v,i]=ch.back();
                ch.pop_back();
                int val=lv[v]-lv[h]+1;
                f.update(i,-val);
                if(!ch.empty())f.update(ch.back().second,val);
            }
            int val=lv[u]-lv[h]+1;
            if(!ch.empty())f.update(ch.back().second,-val);
            ch.emplace_back(u,r);
            f.update(r,val);
        }
        for(auto [l,i]:qr[r]){
            int u=rtin.query(l,r),v=rtout.query(l,r);
            ans[i]=f.query(r)-f.query(l-1)-rdep.query(u,v);
        }
    }
    for(int i=1;i<=q;i++)cout << ans[i] << "\n";
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:103:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |                 auto [v,i]=ch.back();
      |                      ^
tourism.cpp:114:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |         for(auto [l,i]:qr[r]){
      |                  ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 81500 KB Output is correct
2 Correct 25 ms 81500 KB Output is correct
3 Correct 22 ms 81500 KB Output is correct
4 Incorrect 24 ms 81500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 81500 KB Output is correct
2 Correct 25 ms 81500 KB Output is correct
3 Correct 22 ms 81500 KB Output is correct
4 Incorrect 24 ms 81500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 81500 KB Output is correct
2 Incorrect 22 ms 81496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 81592 KB Output is correct
2 Incorrect 103 ms 85556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 81744 KB Output is correct
2 Incorrect 22 ms 81500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 81500 KB Output is correct
2 Correct 25 ms 81500 KB Output is correct
3 Correct 22 ms 81500 KB Output is correct
4 Incorrect 24 ms 81500 KB Output isn't correct
5 Halted 0 ms 0 KB -