Submission #1265378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265378		quangminh412	Tourism (JOI23_tourism)	C++17	28 / 100	5092 ms	14788 KiB

tourism

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

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

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".ans").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 1e5 + 1;
const int maxbit = 17;

vector<int> adj[maxn];
int in[maxn], out[maxn];
int par[maxbit][maxn], d[maxn], c[maxn];
int n, m, q;

int timeDFS = 0;
void DFS(int u, int p = -1)
{
    in[u] = ++timeDFS;
    for (int v : adj[u])
    {
        if (v == p)
            continue;

        d[v] = d[u] + 1;
        par[0][v] = u;
        for (int i = 1; i < maxbit; i++)
            par[i][v] = par[i - 1][par[i - 1][v]];
        DFS(v, u);
    }
    out[u] = timeDFS;
}

int LCA(int u, int v)
{
    if (d[u] < d[v])
        swap(u, v);
    int k = d[u] - d[v];
    for (int i = 0; i < maxbit; i++)
        if (k >> i & 1)
            u = par[i][u];
    if (u == v) return u;
    for (int i = maxbit - 1; i >= 0; i--)
        if (par[i][u] != par[i][v])
        {
            u = par[i][u];
            v = par[i][v];
        }
    return par[0][u];
}

bool cmp(int u, int v)
{
    return in[u] < in[v];
}

void solve()
{
    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);
    }
    for (int i = 1; i <= m; i++)
        cin >> c[i];

    DFS(1);

    while (q--)
    {
        int l, r; cin >> l >> r;

        vector<int> proc;
        for (int i = l; i <= r; i++)
            proc.push_back(c[i]);
        sort(proc.begin(), proc.end(), cmp);
        ll res = 0;
        for (int i = 0; i < (int)proc.size(); i++)
        {
            int u = proc[i];
            res += d[u];
            if (i != 0)
                res -= d[LCA(u, proc[i - 1])];
            else
                res -= d[LCA(u, proc.back())];
        }

        cout << res + 1 << '\n';
    }
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".ans").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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