oj.uz

Submission #865422

# Submission time Handle Problem Language Result Execution time Memory
865422 2023-10-24T08:10:14 Z owoovo Tourism (JOI23_tourism) C++14
24 / 100
 5000 ms 22080 KB 
#include<bits/stdc++.h>
#define pii pair<pair<int,int>,int>
#define F first 
#define S second
using namespace std;
int n,m,q,bit[100010],v[100010],c[100010],dp[25][100010],depth[100010];
vector<int> e[100010];
vector<pii> qu;
bool cmp(pii a, pii b){
    return a.S<b.S;
}
void modify(int x,int p){
    while(p<=m){
        bit[p]+=x;
        p+=p&(-p);
    }
    return ;
}
int que(int p){
    int ans=0;
    while(p){
        ans+=bit[p];
        p-=p&(-p);
    }
    return ans;
}
void dfs(int now,int last){
    dp[0][now]=last;
    depth[now]=depth[last]+1;
    for(auto x:e[now]){
        if(x==last)continue;
        dfs(x,now);
    }
    return;
}
int lca(int a,int b){
    if(depth[a]>depth[b])swap(a,b);
    for(int i=19;i>=0;i--){
        if(depth[a]+(1<<i)<=depth[b]){
            b=dp[i][b];
        }
    }
    if(a==b)return a;
    for(int i=19;i>=0;i--){
        if(dp[i][a]!=dp[i][b]){
            a=dp[i][a];
            b=dp[i][b];
        }
    }
    return dp[0][a];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for(int i=1;i<=m;i++){
        cin>>v[i];
    }
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        if(a==m)b=1;
        qu.push_back({{a,b},i});
    }
    dfs(1,1);
    for(int i=1;i<=19;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][dp[i-1][j]];
        }
    }
    sort(qu.begin(),qu.end());
    int now=q-1;

    for(int i=m-1;i>0;i--){
        
        int p=lca(v[i],v[i+1]);
        
        int nw=v[i];
        while(nw!=p){
            if(c[nw]>0)modify(-1,c[nw]);
            c[nw]=i;
            modify(1,i);
            nw=dp[0][nw];
        }
        nw=v[i+1];
        while(nw!=p){
            if(c[nw]>0)modify(-1,c[nw]);
            c[nw]=i;
            modify(1,i);
            nw=dp[0][nw];
        }
        if(c[p]>0)modify(-1,c[p]);
        c[p]=i;
        modify(1,i);
        while(now>=0&&qu[now].F.F==i){
            if(qu[now].F.F==qu[now].F.S){
                qu[now].F.S=1;
            }else{
                qu[now].F.S=que(qu[now].F.S-1);
            }
            now--;
        }
    }

    sort(qu.begin(),qu.end(),cmp);
    for(auto x:qu){
        cout<<x.F.S<<"\n"; 
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10884 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10888 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10844 KB Output is correct
28 Correct 2 ms 10892 KB Output is correct
29 Incorrect 2 ms 10888 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10884 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10888 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10844 KB Output is correct
28 Correct 2 ms 10892 KB Output is correct
29 Incorrect 2 ms 10888 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 11096 KB Output is correct
3 Correct 2 ms 10896 KB Output is correct
4 Execution timed out 5066 ms 19116 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10884 KB Output is correct
2 Correct 51 ms 14240 KB Output is correct
3 Correct 79 ms 14888 KB Output is correct
4 Correct 65 ms 16980 KB Output is correct
5 Correct 99 ms 19028 KB Output is correct
6 Correct 97 ms 19028 KB Output is correct
7 Correct 96 ms 19060 KB Output is correct
8 Correct 95 ms 19024 KB Output is correct
9 Correct 101 ms 19044 KB Output is correct
10 Correct 97 ms 18980 KB Output is correct
11 Correct 110 ms 19336 KB Output is correct
12 Correct 98 ms 19160 KB Output is correct
13 Correct 102 ms 19476 KB Output is correct
14 Correct 103 ms 19844 KB Output is correct
15 Incorrect 122 ms 22080 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10852 KB Output is correct
4 Correct 113 ms 17604 KB Output is correct
5 Correct 114 ms 17352 KB Output is correct
6 Correct 132 ms 21184 KB Output is correct
7 Correct 137 ms 21936 KB Output is correct
8 Correct 138 ms 21960 KB Output is correct
9 Correct 137 ms 21960 KB Output is correct
10 Correct 142 ms 21956 KB Output is correct
11 Correct 137 ms 21960 KB Output is correct
12 Correct 138 ms 21952 KB Output is correct
13 Correct 138 ms 22004 KB Output is correct
14 Correct 46 ms 14280 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10884 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10888 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 2 ms 10840 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10844 KB Output is correct
28 Correct 2 ms 10892 KB Output is correct
29 Incorrect 2 ms 10888 KB Output isn't correct
30 Halted 0 ms 0 KB -