Submission #1226869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226869		Aviansh	Tourism (JOI23_tourism)	C++20	10 / 100	5094 ms	11068 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;
        i--;
    }
    while(q--){
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        set<int>v;
        for(int i = l;i<=r;i++){
            v.insert(c[i]);
        }
        cout << dfs(c[l],g,-1,v,0)+1 << "\n";
    }
    return 0;
}

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