Submission #1265383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265383		quangminh412	Tourism (JOI23_tourism)	C++17	28 / 100	5091 ms	35180 KiB

tourism

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 1e5 + 5;
const int maxbit = 17;
const int N = 316;

vector<int> adj[maxn];
int in[maxn], out[maxn], rev[maxn];
int par[maxbit][maxn], d[maxn], c[maxn];
int n, m, q;

int fi[maxn];
vector<int> euler, depth;

int timeDFS = 0;
void DFS(int u, int p = -1)
{
    fi[u] = (int)euler.size();
    in[u] = ++timeDFS;
    rev[timeDFS] = u;
    euler.push_back(u);
    depth.push_back(d[u]);
    for (int v : adj[u])
    {
        if (v == p)
            continue;

        d[v] = d[u] + 1;
        par[0][v] = u;
        for (int i = 1; i < maxbit; i++)
            par[i][v] = par[i - 1][par[i - 1][v]];
        DFS(v, u);

        euler.push_back(u);
        depth.push_back(d[u]);
    }
    out[u] = timeDFS;
}

int st[maxbit + 1][2 * maxn], lg[2 * maxn];
void build()
{
    int m = (int)euler.size();
    for (int i = 0; i < m; i++)
        st[0][i] = i;
    for (int k = 1; k <= maxbit; k++)
        for (int i = 0; i + (1 << k) <= m; i++)
        {
            int x = st[k - 1][i], y = st[k - 1][i + (1 << (k - 1))];
            st[k][i] = (depth[x] < depth[y] ? x : y);
        }
}

int segment(int l, int r)
{
    int i = lg[r - l + 1];
    int x = st[i][l], y = st[i][r - (1 << i) + 1];
    return (depth[x] < depth[y] ? x : y);
}

int LCA(int u, int v)
{
    if (fi[u] > fi[v])
        swap(u, v);
    int idx = segment(fi[u], fi[v]);
    return euler[idx];
}

// Mo's algorithm
struct Query
{
    int l, r;
    int id;

    Query() = default;
    Query(int l, int r, int id) : l(l), r(r), id(id) {};
    bool operator < (const Query& other) const
    {
        if (l / N == other.l / N)
            return ((l / N) % 2 == 1 ? r < other.r : r > other.r);
        return l / N < other.l / N;
    }
};
vector<Query> queries;

ll res = 0;
multiset<int> ms;

void add(int u)
{
    // RIGHT
    int L = -1, R = -1;
    auto it = ms.lower_bound(in[u]);
    if (it != ms.end())
    {
        R = rev[*it];
        res -= d[LCA(u, R)];
    }
    // LEFT
    if (it != ms.begin())
    {
        it--;
        L = rev[*it];
        res -= d[LCA(u, L)];
    }

    if (L != -1 && R != -1)
        res += d[LCA(L, R)];

    res += d[u];
    ms.insert(in[u]);
}

void del(int u)
{
    res -= d[u];
    ms.erase(ms.find(in[u]));

    // RIGHT
    int L = -1, R = -1;
    auto it = ms.lower_bound(in[u]);
    if (it != ms.end())
    {
        R = rev[*it];
        res += d[LCA(u, R)];
    }
    // LEFT
    if (it != ms.begin())
    {
        it--;
        L = rev[*it];
        res += d[LCA(u, L)];
    }

    if (L != -1 && R != -1)
        res -= d[LCA(L, R)];
}

void Mo()
{
    sort(queries.begin(), queries.end());
    int curl = queries[0].l, curr = queries[0].l;
    vector<int> ans(q, 0);
    add(c[curl]);

    for (Query &Q : queries)
    {
        int l = Q.l, r = Q.r, id = Q.id;

        while (l < curl) { add(c[--curl]); }
        while (curr < r) { add(c[++curr]); }
        while (curl < l) { del(c[curl++]); }
        while (r < curr) { del(c[curr--]); }

        int u = rev[*ms.begin()], v = rev[*prev(ms.end())];
        ans[id] = res - d[LCA(u, v)] + 1;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

void solve()
{
    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);
    }
    for (int i = 1; i <= m; i++)
        cin >> c[i];

    for (int i = 2; i <= 2 * n; i++)
        lg[i] = lg[i / 2] + 1;
    DFS(1);
    build();

    for (int i = 0; i < q; i++)
    {
        int l, r; cin >> l >> r;

        queries.push_back(Query(l, r, i));
    }

    Mo();
}

Compilation message (stderr)

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