Submission #796276

#	Time	Username	Problem	Language	Result	Execution time	Memory
796276		Johann	Tourism (JOI23_tourism)	C++14	10 / 100	5045 ms	22396 KiB

tourism

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

int N, M, Q;
vi C;
vector<set<int>> CC;
vvi adj;
vi in, out;
vvi vorg;

// void dfs(int v, int p, int &idx);

int solve(int v, int p, int l, int r)
{
    int ans = 0;
    for (int u : adj[v])
        if (u != p)
            ans += solve(u, v, l, r);
    auto it = CC[v].lower_bound(l);
    if ((it != CC[v].end() && *it < r) || ans)
        ++ans;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> Q;

    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    int idx = 0;
    in.resize(N), out.resize(N);
    vorg.assign(N, vi(ceil(log2(N) + 1)));
    // dfs(0, 0, idx);

    C.resize(M), CC.resize(N);
    for (int i = 0; i < M; ++i)
    {
        cin >> C[i];
        --C[i];
        CC[C[i]].insert(i);
    }
    for (int i = 0, l, r; i < Q; ++i)
    {
        cin >> l >> r;
        --l;

        cout << solve(C[l], C[l], l, r) << "\n";
    }
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:42:9: warning: unused variable 'idx' [-Wunused-variable]
   42 |     int idx = 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