oj.uz

Submission #954041

# Submission time Handle Problem Language Result Execution time Memory
954041 2024-03-27T06:46:07 Z owoovo Tourism (JOI23_tourism) C++17
24 / 100
 665 ms 36616 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);
    }
    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 1 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 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 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 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4880 KB Output is correct
11 Correct 1 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 1 ms 4696 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4440 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 4440 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 2 ms 4444 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 2 ms 4524 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Runtime error 5 ms 8968 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 1 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 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 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 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4880 KB Output is correct
11 Correct 1 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 1 ms 4696 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4440 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 4440 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 2 ms 4444 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 2 ms 4524 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Runtime error 5 ms 8968 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 4568 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 80 ms 14616 KB Output is correct
5 Correct 65 ms 17616 KB Output is correct
6 Correct 78 ms 18384 KB Output is correct
7 Correct 100 ms 20876 KB Output is correct
8 Correct 102 ms 20884 KB Output is correct
9 Correct 100 ms 20944 KB Output is correct
10 Correct 107 ms 20936 KB Output is correct
11 Correct 105 ms 20880 KB Output is correct
12 Correct 98 ms 20932 KB Output is correct
13 Correct 98 ms 21372 KB Output is correct
14 Correct 97 ms 20940 KB Output is correct
15 Correct 43 ms 18260 KB Output is correct
16 Runtime error 55 ms 36616 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 187 ms 9896 KB Output is correct
3 Correct 307 ms 10556 KB Output is correct
4 Correct 231 ms 10836 KB Output is correct
5 Correct 423 ms 13924 KB Output is correct
6 Correct 367 ms 13832 KB Output is correct
7 Correct 389 ms 13808 KB Output is correct
8 Correct 363 ms 13908 KB Output is correct
9 Correct 376 ms 13984 KB Output is correct
10 Correct 378 ms 13736 KB Output is correct
11 Correct 366 ms 13876 KB Output is correct
12 Correct 367 ms 13712 KB Output is correct
13 Correct 366 ms 14188 KB Output is correct
14 Correct 373 ms 14348 KB Output is correct
15 Runtime error 50 ms 20816 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 496 ms 12792 KB Output is correct
5 Correct 559 ms 12764 KB Output is correct
6 Correct 585 ms 15032 KB Output is correct
7 Correct 632 ms 16740 KB Output is correct
8 Correct 617 ms 16660 KB Output is correct
9 Correct 642 ms 16584 KB Output is correct
10 Correct 665 ms 16508 KB Output is correct
11 Correct 609 ms 16616 KB Output is correct
12 Correct 618 ms 16840 KB Output is correct
13 Correct 636 ms 16624 KB Output is correct
14 Correct 41 ms 7320 KB Output is correct

Subtask #6
0 / 41.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 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 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 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4880 KB Output is correct
11 Correct 1 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 1 ms 4696 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 2 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4440 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 4440 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 2 ms 4444 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 2 ms 4524 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Runtime error 5 ms 8968 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -