Submission #1001185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001185		LonlyR	Tourism (JOI23_tourism)	C++17	28 / 100	5092 ms	27220 KiB

tourism

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
const int maxn = 1e5 + 5, bl = sqrt(maxn);
int n, m, q, cnt, cur;
int in[maxn], out[maxn], h[maxn], par[18][maxn], id[maxn], c[maxn], ans[maxn], in_set[maxn];
vector<int> adj[maxn];

struct cmp
{
    bool operator() (int x, int y) const
    {
        return in[x] < in[y];
    }
};

set<int, cmp> s;

struct Q{
    int l, r, id;
    bool operator < (Q b) const
    {
        if (l / bl != b.l / bl) return l < b.l;
        return (l / bl & 1) ? (r < b.r) : (r > b.r);
    }
} qr[maxn];

void dfs(int x = 1, int p = 1)
{
    par[0][x] = p;
    h[x] = h[p] + 1;
    for (int i = 1; i < 18; i++)
        par[i][x] = par[i - 1][par[i - 1][x]];
    in[x] = ++cnt;
    for (int i : adj[x]) if (i != p)
        dfs(i, x);
    out[x] = cnt;
}

inline bool sub(int u, int v) /// u in subtree of v
{
    return in[v] <= in[u] && out[u] <= out[v];
}

int lca(int u, int v)
{
    if (h[u] > h[v]) swap(u, v);
    if (sub(v, u)) return u;
    for (int i = 17; i >= 0; i--)
        if (sub(u, par[i][v]) == 0)
            v = par[i][v];
    return par[0][v];
}

int dist(int u, int v, int w = -1)
{
    if (w == -1) return h[u] + h[v] - h[lca(u, v)] * 2;
    return h[u] + h[v] - h[w] * 2;
}

void add(int x)
{
    x = c[x];
    in_set[x]++;
    if (in_set[x] == 1)
    {
        cur += h[x];
        if (s.size() == 0) return s.emplace(x), void();
        auto it = s.lower_bound(x);
        if (it == s.begin())
            cur -= h[lca(x, *it)];
        else if (it == s.end())
            cur -= h[lca(x, *prev(it))];
        else
        {
            auto u = *it, v = *prev(it);
            cur += h[lca(u, v)];
            cur -= h[lca(u, x)];
            cur -= h[lca(v, x)];
        }
    }
    s.emplace(x);
}

void del(int x)
{
    x = c[x];
    in_set[x]--;
    if (in_set[x] == 0)
    {
        cur -= h[x];
        if (s.size() == 1) return s.clear(), void();
        auto it = s.lower_bound(x);
        if (it == s.begin())
            cur += h[lca(x, *next(it))];
        else if (next(it) == s.end())
            cur += h[lca(x, *prev(it))];
        else
        {
            auto u = *prev(it), v = *next(it);
            cur -= h[lca(u, v)];
            cur += h[lca(u, x)];
            cur += h[lca(v, x)];
        }
        s.erase(it);
    }

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1, u, v; i < n; i++)
        cin >> u >> v,
        adj[u].emplace_back(v),
        adj[v].emplace_back(u);
    for (int i = 1; i <= m; i++)
        cin >> c[i], id[i] = (i - 1) / bl + 1;
    dfs();
    for (int i = 1; i <= q; i++)
        cin >> qr[i].l >> qr[i].r, qr[i].id = i;
    sort(qr + 1, qr + q + 1);
    for (int i = 1, l = 1, r = 0; i <= q; i++)
    {
        auto [lx, rx, id] = qr[i];
        while (r < rx) add(++r);
        while (l > lx) add(--l);
        while (r > rx) del(r--);
        while (l < lx) del(l++);
        ans[id] = cur - h[lca(*s.begin(), *s.rbegin())] + 1;
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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