oj.uz

Submission #954042

# Submission time Handle Problem Language Result Execution time Memory
954042 2024-03-27T06:53:37 Z owoovo Tourism (JOI23_tourism) C++17
24 / 100
 719 ms 34660 KB 
#include<bits/stdc++.h>
#define ll long long
#define MP make_pair
#define F first 
#define S second 
using namespace std;
int f[100010],si[100010],hs[100010],top[100010],dep[100010],in[100010],cnt;
int n,m,q;
vector<int> e[100010];
int dfs1(int now,int last){
    dep[now]=dep[last]+1;
    f[now]=last;
    si[now]=1;
    for(auto x:e[now]){
        if(x==last)continue;
        int siz=dfs1(x,now);
        if(siz>si[hs[now]]){
            hs[now]=x;
        }
        si[now]+=siz;
    }
    return si[now];
}
void dfs2(int now,int tp){
    in[now]=++cnt;
    top[now]=tp;
    if(hs[now]!=0)dfs2(hs[now],tp);
    for(auto x:e[now]){
        if(x==f[now]||x==hs[now])continue;
        dfs2(x,x);
    }
    return;
}
struct Bit{
    int ori[100010]={};
    void modify(int p,int x){
        while(p<=100000){
            ori[p]+=x;
            p+=p&(-p);
        }
        return ;
    }
    int query(int p){
        int ans=0;
        while(p){
            ans+=ori[p];
            p-=p&(-p);
        }
        return ans;
    }
}bit;
int ans[100010],ver[100010];
vector<pair<pair<int,int>,int>> qu;
set<pair<pair<int,int>,int>>st;
void segin(int l,int r,int id){
    if(l>r)swap(l,r);
    //cout<<l<<" "<<r<<" "<<id<<" x\n";
    auto oi=st.lower_bound({{l+1,0},0});
    auto tar=oi;
    vector<pair<pair<int,int>,int>> add={};
    vector<set<pair<pair<int,int>,int>>::iterator> del={};
    if(tar!=st.begin()&&(*(prev(tar))).F.S>=l)oi=prev(oi);
    tar=oi;
    //cout<<l<<" "<<r<<" "<<id<<"\n";
    while(tar!=st.end()&&(*tar).F.F<=r){
        auto [x,ID]=*tar;
        auto [L,R]=x;
        del.push_back(tar);
        //cout<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<id<<" "<<ID<<"\n";
        if(l<=L&&R<=r){
            bit.modify(ID,L-R-1);
        }else if(L<l&&R<=r){
            add.push_back(MP(MP(L,l-1),ID));
            bit.modify(ID,l-R-1);
        }else if(l<=L&&r<R){
            add.push_back(MP(MP(r+1,R),ID));
            bit.modify(ID,L-r-1);
        }else{
            add.push_back(MP(MP(L,l-1),ID));
            add.push_back(MP(MP(r+1,R),ID));
            bit.modify(ID,l-r-1);
        }
        tar=next(tar);
    }
    if(del.size()!=0)st.erase(del[0],next(del[del.size()-1]));
    // for(auto x:del){
    //     //cout<<"DEL "<<(*x).F.F<<" "<<(*x).F.S<<" "<<(*x).S<<"\n";
    //     st.erase(x);
    // }
    for(auto x:add){
        //cout<<"ADD "<<x.F.F<<" "<<x.F.S<<" "<<x.S<<"\n";
        st.insert(x);
    }
    st.insert({{l,r},id});
    bit.modify(id,r-l+1);
    return;
}
void putin(int u,int v,int id){
    while(1){
        //cout<<u<<" "<<v<<" "<<id<<"\n";
        if(top[u]==top[v]){
            segin(in[v],in[u],id);
            break;
        }
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        segin(in[top[u]],in[u],id);
        u=f[top[u]];
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        cin>>ver[i];
    }
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        if(l==r){
            ans[i]=1;
            continue;
        }
        qu.push_back({{l,r},i});
    }
    sort(qu.begin(),qu.end());
    reverse(qu.begin(),qu.end());
    int now=0;
    for(int i=m-1;i>=1;i--){
        //cout<<i<<"ok\n";
        //put in i,i+1
        putin(ver[i],ver[i+1],i+1);
        while(now!=q&&qu[now].F.F==i){
            auto [x,id]=qu[now];
            auto [l,r]=x;
            ans[id]=bit.query(r);
            now++;
        }
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Runtime error 4 ms 8796 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Runtime error 4 ms 8796 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 81 ms 13268 KB Output is correct
5 Correct 69 ms 16424 KB Output is correct
6 Correct 77 ms 17096 KB Output is correct
7 Correct 100 ms 19144 KB Output is correct
8 Correct 102 ms 19140 KB Output is correct
9 Correct 105 ms 19092 KB Output is correct
10 Correct 100 ms 19144 KB Output is correct
11 Correct 102 ms 19148 KB Output is correct
12 Correct 95 ms 19544 KB Output is correct
13 Correct 101 ms 19388 KB Output is correct
14 Correct 94 ms 19396 KB Output is correct
15 Correct 38 ms 17244 KB Output is correct
16 Runtime error 55 ms 34660 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 189 ms 9444 KB Output is correct
3 Correct 302 ms 9880 KB Output is correct
4 Correct 233 ms 10064 KB Output is correct
5 Correct 383 ms 13072 KB Output is correct
6 Correct 414 ms 12884 KB Output is correct
7 Correct 367 ms 12864 KB Output is correct
8 Correct 379 ms 12884 KB Output is correct
9 Correct 374 ms 12712 KB Output is correct
10 Correct 367 ms 12852 KB Output is correct
11 Correct 369 ms 12880 KB Output is correct
12 Correct 369 ms 12884 KB Output is correct
13 Correct 388 ms 13112 KB Output is correct
14 Correct 374 ms 13132 KB Output is correct
15 Runtime error 51 ms 19028 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 526 ms 11228 KB Output is correct
5 Correct 524 ms 11468 KB Output is correct
6 Correct 581 ms 13524 KB Output is correct
7 Correct 639 ms 14796 KB Output is correct
8 Correct 661 ms 14852 KB Output is correct
9 Correct 719 ms 14656 KB Output is correct
10 Correct 636 ms 14792 KB Output is correct
11 Correct 661 ms 14792 KB Output is correct
12 Correct 626 ms 14792 KB Output is correct
13 Correct 710 ms 14960 KB Output is correct
14 Correct 41 ms 6352 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Runtime error 4 ms 8796 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -