Submission #829284

#	Time	Username	Problem	Language	Result	Execution time	Memory
829284		Hanksburger	Tourism (JOI23_tourism)	C++17	10 / 100	5040 ms	18140 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
int par[100005][20], depth[100005], tin[100005], val[100005], c[100005], n, m, q, t;
vector<pair<int, int> > vec;
vector<int> adj[100005];
void dfs(int u, int p)
{
    par[u][0]=p;
    for (int i=1; i<20; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    tin[u]=(++t);
    for (int v:adj[u])
    {
        if (v==p)
            continue;
        depth[v]=depth[u]+1;
        dfs(v, u);
    }
}
void dfs2(int u, int p)
{
    for (int v:adj[u])
    {
        if (v==p)
            continue;
        dfs2(v, u);
        val[u]+=val[v];
    }
}
int lca(int u, int v)
{
    if (depth[u]<depth[v])
        swap(u, v);
    for (int i=19; i>=0; i--)
        if ((depth[u]-depth[v])&(1<<i))
            u=par[u][i];
    if (u==v)
        return u;
    for (int i=19; i>=0; i--)
        if (par[u][i]!=par[v][i])
            u=par[u][i], v=par[v][i];
    return par[u][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    for (int i=1; i<=m; i++)
        cin >> c[i];
    for (int i=1; i<=q; i++)
    {
        int l, r, ans=0;
        cin >> l >> r;
        if (l==r)
        {
            cout << 1 << '\n';
            continue;
        }
        for (int j=1; j<=n; j++)
            val[j]=0;
        vec.clear();
        for (int j=l; j<=r; j++)
            vec.push_back({tin[c[j]], c[j]});
        sort(vec.begin(), vec.end());
        for (int j=1; j<vec.size(); j++)
        {
            val[vec[j-1].second]++;
            val[vec[j].second]++;
        //    cout << "val " << vec[j-1].second << " +1\n";
        //    cout << "val " << vec[j].second << " +1\n";
            int LCA=lca(vec[j-1].second, vec[j].second);
            if (LCA!=1)
            {
                val[par[LCA][0]]-=2;
        //        cout << "val " << par[LCA][0] << " -2\n";
            }
        }
        dfs2(1, 1);
        for (int j=1; j<=n; j++)
            if (val[j])
                ans++;
        cout << ans << '\n';
    }
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:75:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j=1; j<vec.size(); j++)
      |                       ~^~~~~~~~~~~

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