Submission #1303094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303094		tonytung_123	Tourism (JOI23_tourism)	C++20	28 / 100	5096 ms	44424 KiB

tourism

#include <bits/stdc++.h>
#define task "Tourism"
#define ll long long
#define fi first
#define se second
#define ld long double
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
using namespace std;

struct Query
{
    int l, r, i;
};

const int N = 1e5 + 5, LG = 19, B = 316;
vector<int> ad[N];
set<pii> nodes;
int n, m, q, tin[N], d[N], c[N], cnt[N], ans[N], timer = 0, tot = 0;
pii rmq[LG+1][2*N];
Query que[N];

void dfs(int u, int p)
{
    tin[u] = ++timer;
    rmq[0][timer] = {d[u], u};
    for (int v : ad[u])
    {
        if (v == p) continue;
        d[v] = d[u] + 1;
        dfs(v, u);
    }
    if (p != 0) rmq[0][++timer] = {d[p], p};
}

int lca(int u, int v)
{
    int l = tin[u], r = tin[v];
    if (l > r) swap(l, r);
    int k = __lg(r-l+1);
    return min(rmq[k][l], rmq[k][r-(1<<k)+1]).se;
}

int dist(int u, int v)
{
    return d[u] + d[v] - 2*d[lca(u, v)];
}

pii find(int u)
{
    auto it = nodes.lower_bound({tin[u], -1});
    pii res;
    if (it == nodes.end())
    {
        --it;
        res.fi = (*it).se;
        res.se = (*nodes.begin()).se;
    }
    else if (it == nodes.begin())
    {
        res.fi = (*it).se;
        res.se = (*nodes.rbegin()).se;
    }
    else
    {
        res.fi = (*it).se;
        --it;
        res.se = (*it).se;
    }
    return res;
}

void add(int u)
{
    if (++cnt[u] != 1) return;
    if (nodes.size() == 0) nodes.insert({tin[u], u});
    else if (nodes.size() == 1)
    {
        int v = (*nodes.begin()).se;
        tot += 2*dist(u, v);
        nodes.insert({tin[u], u});
    }
    else
    {
        auto [v1, v2] = find(u);
        tot += dist(v1, u) + dist(u, v2) - dist(v1, v2);
        nodes.insert({tin[u], u});
    }
}

void del(int u)
{
    if (--cnt[u] != 0) return;
    if (nodes.size() == 1) nodes.erase(nodes.find({tin[u], u}));
    else if (nodes.size() == 2)
    {
        nodes.erase(nodes.find({tin[u], u}));
        tot = 0;
    }
    else
    {
        nodes.erase(nodes.find({tin[u], u}));
        auto [v1, v2] = find(u);
        tot -= dist(v1, u) + dist(u, v2) - dist(v1, v2);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    dfs(1, 0);
    for (int j = 1; j <= LG; j++)
        for (int i = 1; i+(1<<j)-1 < 2*n; i++) rmq[j][i] = min(rmq[j-1][i], rmq[j-1][i+(1<<(j-1))]);
    for (int i = 1; i <= m; i++) cin >> c[i];
    for (int i = 1; i <= q; i++)
    {
        cin >> que[i].l >> que[i].r;
        que[i].i = i;
    }
    sort(que+1, que+q+1, [&](const Query &x, const Query &y)
    {
        if (x.l/B != y.l/B) return x.l/B < y.l/B;
        return (x.l/B&1) ? x.r < y.r : x.r > y.r;
    });
    int l = 1, r = 0;
    for (int i = 1; i <= q; i++)
    {
        while (l > que[i].l) add(c[--l]);
        while (r < que[i].r) add(c[++r]);
        while (l < que[i].l) del(c[l++]);
        while (r > que[i].r) del(c[r--]);
        ans[que[i].i] = tot/2+1;
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';

    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".out", "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