oj.uz

답안 #865429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865429 2023-10-24T08:16:00 Z owoovo Tourism (JOI23_tourism) C++14
0 / 100
 110 ms 17784 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 49 ms 13160 KB Output is correct
3 Correct 84 ms 13744 KB Output is correct
4 Correct 64 ms 15956 KB Output is correct
5 Correct 95 ms 17236 KB Output is correct
6 Correct 95 ms 17232 KB Output is correct
7 Correct 95 ms 17236 KB Output is correct
8 Correct 103 ms 17768 KB Output is correct
9 Correct 101 ms 17116 KB Output is correct
10 Correct 99 ms 17268 KB Output is correct
11 Correct 94 ms 17300 KB Output is correct
12 Correct 101 ms 17272 KB Output is correct
13 Incorrect 110 ms 17784 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10840 KB Output is correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -