oj.uz

Submission #924666

# Submission time Handle Problem Language Result Execution time Memory
924666 2024-02-09T11:49:53 Z ttamx Tourism (JOI23_tourism) C++14
24 / 100
 221 ms 184948 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[M];
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<=m;r++){
        int cnt=0;
        for(int u=c[r];u;u=pa[u]){
            assert(cnt++<LG);
            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:105:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |                 auto [v,i]=ch.back();
      |                      ^
tourism.cpp:116:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |         for(auto [l,i]:qr[r]){
      |                  ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 82260 KB Output is correct
2 Correct 21 ms 82524 KB Output is correct
3 Correct 22 ms 82260 KB Output is correct
4 Correct 23 ms 82472 KB Output is correct
5 Correct 23 ms 82524 KB Output is correct
6 Correct 22 ms 82524 KB Output is correct
7 Correct 22 ms 82524 KB Output is correct
8 Correct 23 ms 82524 KB Output is correct
9 Correct 22 ms 82520 KB Output is correct
10 Correct 22 ms 82512 KB Output is correct
11 Correct 22 ms 82512 KB Output is correct
12 Correct 24 ms 82508 KB Output is correct
13 Correct 22 ms 82532 KB Output is correct
14 Correct 22 ms 82352 KB Output is correct
15 Runtime error 89 ms 166924 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 82260 KB Output is correct
2 Correct 21 ms 82524 KB Output is correct
3 Correct 22 ms 82260 KB Output is correct
4 Correct 23 ms 82472 KB Output is correct
5 Correct 23 ms 82524 KB Output is correct
6 Correct 22 ms 82524 KB Output is correct
7 Correct 22 ms 82524 KB Output is correct
8 Correct 23 ms 82524 KB Output is correct
9 Correct 22 ms 82520 KB Output is correct
10 Correct 22 ms 82512 KB Output is correct
11 Correct 22 ms 82512 KB Output is correct
12 Correct 24 ms 82508 KB Output is correct
13 Correct 22 ms 82532 KB Output is correct
14 Correct 22 ms 82352 KB Output is correct
15 Runtime error 89 ms 166924 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 82512 KB Output is correct
2 Correct 22 ms 82776 KB Output is correct
3 Correct 24 ms 82536 KB Output is correct
4 Runtime error 131 ms 184948 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82508 KB Output is correct
2 Runtime error 100 ms 171340 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82456 KB Output is correct
2 Correct 25 ms 82520 KB Output is correct
3 Correct 26 ms 82512 KB Output is correct
4 Correct 175 ms 88248 KB Output is correct
5 Correct 176 ms 87892 KB Output is correct
6 Correct 221 ms 89452 KB Output is correct
7 Correct 208 ms 90004 KB Output is correct
8 Correct 197 ms 90192 KB Output is correct
9 Correct 203 ms 90116 KB Output is correct
10 Correct 209 ms 90192 KB Output is correct
11 Correct 207 ms 90084 KB Output is correct
12 Correct 203 ms 90048 KB Output is correct
13 Correct 194 ms 90144 KB Output is correct
14 Correct 58 ms 85004 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 82260 KB Output is correct
2 Correct 21 ms 82524 KB Output is correct
3 Correct 22 ms 82260 KB Output is correct
4 Correct 23 ms 82472 KB Output is correct
5 Correct 23 ms 82524 KB Output is correct
6 Correct 22 ms 82524 KB Output is correct
7 Correct 22 ms 82524 KB Output is correct
8 Correct 23 ms 82524 KB Output is correct
9 Correct 22 ms 82520 KB Output is correct
10 Correct 22 ms 82512 KB Output is correct
11 Correct 22 ms 82512 KB Output is correct
12 Correct 24 ms 82508 KB Output is correct
13 Correct 22 ms 82532 KB Output is correct
14 Correct 22 ms 82352 KB Output is correct
15 Runtime error 89 ms 166924 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -