Submission #1226900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226900		Aviansh	Tourism (JOI23_tourism)	C++20	7 / 100	69 ms	22344 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

int dfs(int st, vector<int>g[], int p, set<int>&v, int d){
    int ret = 0;
    for(int i : g[st]){
        if(i==p)
            continue;
        int x = dfs(i,g,st,v,d+1);
        ret+=x;
        if(x){
            if(ret>x){
                ret-=d;
            }
        }
    }
    if(v.find(st)!=v.end()){
        return max(ret,d);
    }
    return ret;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int>g[n];
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int c[m];
    for(int &i : c){
        cin >> i;
    }

    const int lg = 20;

    int sparsemax[m][lg];
    int sparsemin[m][lg];
    for(int i = m-1;i>=0;i--){
        sparsemax[i][0]=c[i];
        sparsemin[i][0]=c[i];
        for(int j = 1;j<lg;j++){
            sparsemax[i][j]=max(sparsemax[i][j-1],sparsemax[min(m-1,i+(1<<(j-1)))][j-1]);
            sparsemin[i][j]=min(sparsemin[i][j-1],sparsemin[min(m-1,i+(1<<(j-1)))][j-1]);
        }

    }

    while(q--){
        int l,r;
        cin >> l >> r;
        l--;
        int mx = -1;
        int mn = 1e9;
        for(int i = lg-1;i>=0;i--){
            if(l+(1<<i)<=r){
                mx=max(mx,sparsemax[l][i]);
                mn=min(mn,sparsemin[l][i]);
                l+=(1<<i);
            }
        }
        cout << mx-mn+1 << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41