oj.uz

Submission #954033

# Submission time Handle Problem Language Result Execution time Memory
954033 2024-03-27T06:35:36 Z owoovo Tourism (JOI23_tourism) C++17
24 / 100
 632 ms 37340 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()&&(*(--tar)).F.S>=l)--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++;
    }
    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 4540 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 2 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4532 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 2 ms 4600 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 4444 KB Output is correct
25 Correct 2 ms 4656 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 5 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 1 ms 4444 KB Output is correct
2 Correct 1 ms 4540 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 2 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4532 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 2 ms 4600 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 4444 KB Output is correct
25 Correct 2 ms 4656 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 5 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 75 ms 15312 KB Output is correct
5 Correct 65 ms 18388 KB Output is correct
6 Correct 76 ms 19428 KB Output is correct
7 Correct 98 ms 21956 KB Output is correct
8 Correct 101 ms 21960 KB Output is correct
9 Correct 100 ms 21960 KB Output is correct
10 Correct 105 ms 22068 KB Output is correct
11 Correct 100 ms 21960 KB Output is correct
12 Correct 94 ms 22016 KB Output is correct
13 Correct 96 ms 22212 KB Output is correct
14 Correct 101 ms 22064 KB Output is correct
15 Correct 38 ms 18768 KB Output is correct
16 Runtime error 54 ms 37340 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 2 ms 4444 KB Output is correct
2 Correct 189 ms 10084 KB Output is correct
3 Correct 298 ms 11076 KB Output is correct
4 Correct 234 ms 11228 KB Output is correct
5 Correct 376 ms 14928 KB Output is correct
6 Correct 366 ms 14416 KB Output is correct
7 Correct 371 ms 14668 KB Output is correct
8 Correct 363 ms 14420 KB Output is correct
9 Correct 376 ms 14568 KB Output is correct
10 Correct 369 ms 14416 KB Output is correct
11 Correct 384 ms 14500 KB Output is correct
12 Correct 373 ms 14672 KB Output is correct
13 Correct 398 ms 14764 KB Output is correct
14 Correct 377 ms 15164 KB Output is correct
15 Runtime error 62 ms 21764 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 4656 KB Output is correct
4 Correct 489 ms 13580 KB Output is correct
5 Correct 536 ms 13760 KB Output is correct
6 Correct 621 ms 16376 KB Output is correct
7 Correct 632 ms 17864 KB Output is correct
8 Correct 611 ms 17592 KB Output is correct
9 Correct 607 ms 17648 KB Output is correct
10 Correct 620 ms 17648 KB Output is correct
11 Correct 622 ms 17772 KB Output is correct
12 Correct 611 ms 17644 KB Output is correct
13 Correct 616 ms 17540 KB Output is correct
14 Correct 42 ms 7528 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 4540 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 2 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4532 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 2 ms 4600 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 4444 KB Output is correct
25 Correct 2 ms 4656 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 5 ms 8796 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -