Submission #1306531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306531		Bahamin	Tourism (JOI23_tourism)	C++20	100 / 100	882 ms	23732 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;
const int SQ = 330;

vector<int> adj[MAX_N];
int st[MAX_N];
int timer = 0;
int h[MAX_N];
int par[MAX_N];
int heavy[MAX_N];
int head[MAX_N];
int sz[MAX_N];

void dfs(int u, int p)
{
    par[u] = p;
    sz[u] = 1;
    for (int v : adj[u]) if (v != p)
    {
        h[v] = h[u] + 1;
        dfs(v, u);
        sz[u] += sz[v];
        if (heavy[u] == 0 || sz[heavy[u]] < sz[v]) heavy[u] = v;
    }
}

void decompose(int u, int p, int he)
{
    st[u] = timer++;
    head[u] = he;
    if (heavy[u]) decompose(heavy[u], u, he);
    for (int v : adj[u]) if (v != p && v != heavy[u]) decompose(v, u, v);
}

set<pair<pair<int, int>, int>> al;
int fen[MAX_N];

void add(int x, int y)
{
    x++;
    for (int i = x; i < MAX_N; i += i & (-i)) fen[i] += y;
}

int get(int x)
{
    x++;
    int ans = 0;
    for (int i = x; i > 0; i -= i & (-i)) ans += fen[i];
    return ans;
}

void set1(int l, int r, int x)
{
    auto ind = al.lower_bound({{l, 0}, 0});
    while (ind != al.end() && (*ind).first.first <= r)
    {
        auto xx = *ind;
        if ((*ind).first.second > r)
        {
            add(xx.second, -(r - xx.first.first + 1));
            al.erase(xx);
            al.insert({{r + 1, xx.first.second}, xx.second});
            ind = al.lower_bound({{l, 0}, 0});
            break;
        }
        add(xx.second, -(xx.first.second - xx.first.first + 1));
        al.erase(xx);
        ind = al.lower_bound({{l, 0}, 0});
    }
    if (ind != al.begin())
    {
        ind--;
        if ((*ind).first.second > r)
        {
            auto xx = *ind;
            add(xx.second, -(r - l + 1));
            al.erase(xx);
            al.insert({{xx.first.first, l - 1}, xx.second});
            al.insert({{r + 1, xx.first.second}, xx.second});
        } else if ((*ind).first.second >= l)
        {
            auto xx = *ind;
            add(xx.second, -(xx.first.second - l + 1));
            al.erase(xx);
            al.insert({{xx.first.first, l - 1}, xx.second});
        }
    }
    al.insert({{l, r}, x});
    add(x, r - l + 1);
}

void set2(int u, int v, int x)
{
    for (; head[u] != head[v]; v = par[head[v]])
    {
        if (h[head[u]] > h[head[v]]) swap(u, v);
        set1(st[head[v]], st[v], x);
    }
    if (h[u] < h[v]) swap(u, v);
    if (st[v] < st[u]) set1(st[v] + 1, st[u], x); 
}

void solve() {
    int n, m, q;
    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);
    }
    int c[m];
    for (int i = 0; i < m; i++) cin >> c[i];
    int ans[q];
    vector<pair<int, int>> qs[m];
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        qs[r].push_back({l, i});
    }
    dfs(1, 0);
    decompose(1, 0, 1);
    al.insert({{1, n - 1}, 0});
    add(0, n - 1);
    for (int i = 0; i < m; i++)
    {
        if (i) set2(c[i - 1], c[i], i);
        for (auto x : qs[i]) ans[x.second] = n - get(x.first);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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