oj.uz

Submission #954230

# Submission time Handle Problem Language Result Execution time Memory
954230 2024-03-27T13:11:40 Z owoovo Tourism (JOI23_tourism) C++17
24 / 100
 659 ms 37548 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){
        if(p==0)return ;
        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 2 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 3 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Correct 1 ms 4524 KB Output is correct
20 Correct 1 ms 4632 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 2 ms 4444 KB Output is correct
24 Correct 1 ms 4444 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 4568 KB Output is correct
28 Correct 1 ms 4440 KB Output is correct
29 Runtime error 6 ms 8792 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 2 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 3 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Correct 1 ms 4524 KB Output is correct
20 Correct 1 ms 4632 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 2 ms 4444 KB Output is correct
24 Correct 1 ms 4444 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 4568 KB Output is correct
28 Correct 1 ms 4440 KB Output is correct
29 Runtime error 6 ms 8792 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 80 ms 15112 KB Output is correct
5 Correct 65 ms 18384 KB Output is correct
6 Correct 80 ms 19272 KB Output is correct
7 Correct 102 ms 22000 KB Output is correct
8 Correct 100 ms 21956 KB Output is correct
9 Correct 102 ms 21956 KB Output is correct
10 Correct 100 ms 21960 KB Output is correct
11 Correct 118 ms 21968 KB Output is correct
12 Correct 106 ms 22020 KB Output is correct
13 Correct 96 ms 22212 KB Output is correct
14 Correct 97 ms 22212 KB Output is correct
15 Correct 37 ms 18732 KB Output is correct
16 Runtime error 54 ms 37548 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 4700 KB Output is correct
2 Correct 185 ms 10064 KB Output is correct
3 Correct 323 ms 11436 KB Output is correct
4 Correct 231 ms 11344 KB Output is correct
5 Correct 377 ms 14860 KB Output is correct
6 Correct 368 ms 14464 KB Output is correct
7 Correct 385 ms 14412 KB Output is correct
8 Correct 369 ms 14420 KB Output is correct
9 Correct 373 ms 14628 KB Output is correct
10 Correct 368 ms 14572 KB Output is correct
11 Correct 381 ms 14764 KB Output is correct
12 Correct 374 ms 14432 KB Output is correct
13 Correct 387 ms 14740 KB Output is correct
14 Correct 387 ms 15516 KB Output is correct
15 Runtime error 51 ms 21748 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 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 504 ms 13500 KB Output is correct
5 Correct 555 ms 13532 KB Output is correct
6 Correct 593 ms 16656 KB Output is correct
7 Correct 656 ms 17608 KB Output is correct
8 Correct 645 ms 17584 KB Output is correct
9 Correct 640 ms 17640 KB Output is correct
10 Correct 643 ms 17660 KB Output is correct
11 Correct 622 ms 17700 KB Output is correct
12 Correct 659 ms 17784 KB Output is correct
13 Correct 618 ms 17664 KB Output is correct
14 Correct 44 ms 7380 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Correct 1 ms 4524 KB Output is correct
20 Correct 1 ms 4632 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 2 ms 4444 KB Output is correct
24 Correct 1 ms 4444 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 4568 KB Output is correct
28 Correct 1 ms 4440 KB Output is correct
29 Runtime error 6 ms 8792 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -