Submission #763703

#	Time	Username	Problem	Language	Result	Execution time	Memory
763703		anhduc2701	Tourism (JOI23_tourism)	C++17	100 / 100	1014 ms	111740 KiB

tourism

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int tin[maxn];
int tout[maxn];
int eu[maxn];
int n, m, q;
int ti = 0;
vector<int> G[maxn];
int h[maxn];
void dfs(int u, int pa)
{
    tin[u] = ++ti;
    eu[ti] = u;
    for (auto v : G[u])
    {
        if (v == pa)
            continue;
        h[v] = h[u] + 1;
        dfs(v, u);
        eu[++ti] = u;
    }
}
pair<int, int> rmq[maxn][19];
void init()
{
    for (int i = 1; i <= ti; i++)
    {
        rmq[i][0] = {tin[eu[i]], eu[i]};
    }
    for (int j = 1; (1 << j) <= ti; j++)
    {
        for (int i = 1; i <= ti; i++)
        {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int LCA(int u, int v)
{
    if (tin[u] > tin[v])
        swap(u, v);
    int k = 31 - __builtin_clz(tin[v] - tin[u] + 1);
    return min(rmq[tin[u]][k], rmq[tin[v] - (1 << k) + 1][k]).se;
}
struct que
{
    int l, r, id;
    que() {}
    que(int _l, int _r, int _id)
    {
        l = _l;
        r = _r;
        id = _id;
    }
};
// BIT
int bit[maxn];
void update(int id, int val)
{
    for (id; id >= 1; id -= id & (-id))
    {
        bit[id] += val;
    }
}
int get(int id)
{
    int res = 0;
    for (id; id <= m; id += id & (-id))
    {
        res += bit[id];
    }
    return res;
}
vector<que> st[maxn];
void update(int l, int r, int u, int v, int id)
{
    if (l <= r)
    {
        int mid = (l + r) / 2;
        if (u <= mid && mid <= v)
        {
            st[mid].pb(que(u, v, id));
            return;
        }
        if (v < mid)
            update(l, mid - 1, u, v, id);
        else
            update(mid + 1, r, u, v, id);
    }
}
vector<int> d[maxn];
vector<int> adj[maxn];
int befmid[maxn];
int aftmid[maxn];
int prefbef[maxn];
int prefaft[maxn];
vector<pair<int, int>> ask[maxn];
vector<pair<int, int>> ques[maxn];
void dfs1(int u, int pa, int mid, int l, int r)
{
    auto z = lower_bound(d[u].begin(), d[u].end(), mid) - d[u].begin();

    if (z < d[u].size())
    {
        aftmid[u] = d[u][z];
    }
    else
    {
        aftmid[u] = 1e9;
    }
    if (z != 0)
    {
        z--;
        befmid[u] = d[u][z];
    }

    for (auto v : adj[u])
    {
        if (v == pa)
            continue;
        dfs1(v, u, mid, l, r);

        befmid[u] = max(befmid[v], befmid[u]);
        aftmid[u] = min(aftmid[u], aftmid[v]);

        if (befmid[v] >= l)
        {
            prefbef[befmid[v]] += abs(h[v] - h[u]);
        }

        if (aftmid[v] <= r)
        {
            prefaft[aftmid[v]] += abs(h[v] - h[u]);
        }

        if (befmid[v] >= l && aftmid[v] <= r)
        {
            ask[aftmid[v]].pb({befmid[v], abs(h[v] - h[u])});
        }
    }
}
int ans[maxn];
int c[maxn];
bool cmp(int u, int v)
{
    return tin[u] < tin[v];
}
void DNC(int l, int r)
{
    if (l <= r)
    {

        int mid = (l + r) / 2;
        vector<int> ver;
        for (int i = l; i <= r; i++)
        {
            ver.pb(c[i]);
        }
        sort(ver.begin(), ver.end());
        ver.resize(distance(ver.begin(), unique(ver.begin(), ver.end())));
        sort(ver.begin(), ver.end(), cmp);
        vector<int> vir;
        vir = ver;
        for (auto i = 1; i < ver.size(); i++)
        {
            vir.pb(LCA(ver[i], ver[i - 1]));
        }
        sort(vir.begin(), vir.end());
        vir.resize(distance(vir.begin(), unique(vir.begin(), vir.end())));
        sort(vir.begin(), vir.end(), cmp);

        for (int i = 1; i < vir.size(); i++)
        {
            adj[LCA(vir[i], vir[i - 1])].pb(vir[i]);
            adj[vir[i]].pb(LCA(vir[i], vir[i - 1]));
        }
        dfs1(c[mid], -1, mid, l, r);
        for (int i = mid; i >= l; i--)
        {
            prefbef[i] += prefbef[i + 1];
        }
        for (int i = mid; i <= r; i++)
        {
            prefaft[i] += prefaft[i - 1];
        }
        for (auto v : st[mid])
        {
            ques[v.r].pb({v.l, v.id});
        }
        for (int i = mid; i <= r; i++)
        {
            for (auto v : ask[i])
            {
                update(v.fi, v.se);
            }
            for (auto v : ques[i])
            {
                ans[v.se] = prefbef[v.fi] + prefaft[i] - get(v.fi);
            }
            ques[i].clear();
        }
        for (int i = mid; i >= l; i--)
        {
            prefbef[i] = 0;
        }
        for (int i = mid; i <= r; i++)
        {
            prefaft[i] = 0;
            for (auto v : ask[i])
            {
                update(v.fi, -v.se);
            }
            ask[i].clear();
        }
        for (auto v : vir)
        {
            aftmid[v] = 0;
            befmid[v] = 0;
            adj[v].clear();
        }

        if (l != r)
        {
            DNC(l, mid - 1);
            DNC(mid + 1, r);
        }
    }
}

signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> c[i];
        d[c[i]].pb(i);
    }
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        update(1, m, l, r, i);
    }
    dfs(1, -1);
    init();

    DNC(1, m);
    for (int i = 1; i <= q; i++)
    {
        cout << ans[i] + 1 << "\n";
    }
}

Compilation message (stderr)

tourism.cpp: In function 'void update(int, int)':
tourism.cpp:90:10: warning: statement has no effect [-Wunused-value]
   90 |     for (id; id >= 1; id -= id & (-id))
      |          ^~
tourism.cpp: In function 'int get(int)':
tourism.cpp:98:10: warning: statement has no effect [-Wunused-value]
   98 |     for (id; id <= m; id += id & (-id))
      |          ^~
tourism.cpp: In function 'void dfs1(int, int, int, int, int)':
tourism.cpp:133:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     if (z < d[u].size())
      |         ~~^~~~~~~~~~~~~
tourism.cpp: In function 'void DNC(int, int)':
tourism.cpp:194:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |         for (auto i = 1; i < ver.size(); i++)
      |                          ~~^~~~~~~~~~~~
tourism.cpp:202:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         for (int i = 1; i < vir.size(); i++)
      |                         ~~^~~~~~~~~~~~

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