제출 #970526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970526		vjudge1	Tourism (JOI23_tourism)	C++17	100 / 100	254 ms	27280 KiB

tourism

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 4;
int n, m, a, b, q, l, r, fw[maxn], city[maxn], res[maxn];
int par[maxn], sz[maxn], dep[maxn], nxt[maxn];
int curchain = 1, curpos = 0, head[maxn], chain[maxn], pos[maxn];
bool visited[maxn];
vector<int> adj[maxn];
vector<pair<int, int>> query[maxn];
//basic hld :3
void dfs (int u)
{
    sz[u] = 1;
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v])
        {
            par[v] = u;
            dep[v] = dep[u] + 1;
            dfs(v);
            sz[u] += sz[v];
            if (nxt[u] == 0 || sz[v] > sz[nxt[u]]) nxt[u] = v;
        }
}
void hld (int u)
{
    if (!head[curchain]) head[curchain] = u;
    chain[u] = curchain;
    pos[u] = ++curpos;
    if (nxt[u] != 0) hld(nxt[u]);
    for (int v : adj[u])
        if (v != par[u] && v != nxt[u])
        {
            curchain++;
            hld(v);
        }
}
//fenwick tree to answer the queries
void upd (int idx, int val)
{
    while (idx <= m)
    {
        fw[idx] += val;
        idx += (idx & (-idx));
    }
}
int get (int idx)
{
    int res = 0;
    while (idx > 0)
    {
        res += fw[idx];
        idx -= (idx & (-idx));
    }
    return res;
}
//updating the path from u to v with the corresponding time
struct Event
{
    int l, r, t;
    bool operator < (const Event& other) const
    {
        return l < other.l;
    }
};
multiset<Event> line[maxn]; //each multiset manages a chain (hopefully i understand this correctly)
void update (int u, int v, int t)
{
    while (chain[u] != chain[v])
    {
        if (chain[u] < chain[v]) swap(u, v);
        Event e = {pos[head[chain[u]]], pos[u], t};
        int id = chain[u];
        while (!line[id].empty())
        {
            auto it = line[id].begin();
            Event f = *it;
            if (f.l > e.r) break;
            upd(f.t, -(f.r - f.l + 1));
            line[id].erase(it);
            if (f.r > e.r)
            {
                f.l = e.r + 1;
                line[id].insert(f);
                upd(f.t, f.r - e.r);
            }
            //remember the event e always start at the head of the chain so e.l <= f.l
        }
        upd(e.t, e.r - e.l + 1);
        line[id].insert(e);
        u = par[head[chain[u]]];
    }
    if (pos[u] > pos[v]) swap(u, v);
    Event e = {pos[u], pos[v], t};
    int id = chain[u];
    while (!line[id].empty())
    {
        auto it = line[id].upper_bound(e);
        if (it == line[id].begin()) break;
        it--;
        Event f = *it;
        if (f.r < e.l) break;
        upd(f.t, -(f.r - f.l + 1));
        line[id].erase(it);
        if (f.r > e.r)
        {
            int prevfl = f.l;
            f.l = e.r + 1;
            upd(f.t, f.r - e.r);
            line[id].insert(f);
            f.r = e.r;
            f.l = prevfl;
        }
        if (f.l < e.l)
        {
            f.r = e.l - 1;
            upd(f.t, f.r - f.l + 1);
            line[id].insert(f);
        }
    }
    while (!line[id].empty())
    {
        auto it = line[id].lower_bound(e);
        if (it == line[id].end()) break;
        Event f = *it;
        if (f.l > e.r) break;
        upd(f.t, -(f.r - f.l + 1));
        line[id].erase(it);
        if (f.r > e.r)
        {
            f.l = e.r + 1;
            upd(f.t, f.r - f.l + 1);
            line[id].insert(f);
        }
        //again, e.l <= f.l
    }
    upd(e.t, e.r - e.l + 1);
    line[id].insert(e);
}
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= m; i++) cin >> city[i];
    for (int i = 1; i <= q; i++)
    {
        cin >> l >> r;
        if (l == r) res[i] = 1;
        else query[r].push_back({l, i});
    }
    dfs(1);
    hld(1);
    for (int i = 2; i <= m; i++)
    {
        update(city[i], city[i - 1], i - 1);
        for (pair<int, int> p : query[i])
            res[p.second] = get(i) - get(p.first - 1);
    }
    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}

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