Submission #1265844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265844		quangminh412	Tourism (JOI23_tourism)	C++17	34 / 100	5090 ms	20096 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 oo = 0x3f3f3f3f;
const int maxn = 1e5 + 1;

struct FenwickTree
{
    vector<int> bits;
    int n;

    FenwickTree(int n) : n(n) { bits.resize(n + 1, 0); }

    void update(int pos, int val)
    {
        for (; pos <= n; pos += (pos & (-pos)))
            bits[pos] += val;
    }

    int query(int pos)
    {
        int res = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
            res += bits[pos];
        return res;
    }
    int query(int l, int r) { return query(r) - query(l - 1); }
};

vector<int> adj[maxn], queries[maxn];
int c[maxn], ans[maxn], L[maxn];
FenwickTree bit(maxn);
int n, m, q;

// tree processing
int pos[maxn], tp[maxn], sz[maxn], par[maxn], d[maxn];

void DFS(int u, int p = -1)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p)
            continue;

        par[v] = u;
        d[v] = d[u] + 1;
        DFS(v, u);
        sz[u] += sz[v];
    }
}

int timeDFS = 0;
void DFS_HLD(int u, int top)
{
    pos[u] = ++timeDFS;
    tp[u] = top;

    int nxt = -1;
    for (int v : adj[u])
        if (v != par[u] && (nxt == -1 || sz[v] > sz[nxt]))
            nxt = v;
    if (nxt != -1)
        DFS_HLD(nxt, top);
    for (int v : adj[u])
        if (v != par[u] && v != nxt)
            DFS_HLD(v, v);
}

// handle queries
int R[maxn], X[maxn];
set<int> se;

void update(int l, int r, int x)
{
//    cout << l << ' ' << r << ' ' << x << '\n' << '\n';
//    cout << "Before update:\n";
//    for (array<int, 3> it : se)
//        cout << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
//    cout << "\n";
//    cout << "During update:\n";
    vector<int> pending, deleted;
    auto it = se.upper_bound(r);
    while (it != se.begin())
    {
        it--;
        int u = (*it), v = R[u], val = X[u];
//        cout << u << ' ' <<v  << ' ' << val << '\n';

        if (v < l)
            break;
        deleted.push_back(u);
        int le = max(u, l), ri = min(v, r);
        bit.update(val + 1, -(ri - le + 1));
        R[le] = ri; X[le] = x;
        pending.push_back(le);
        if (u < l)
        {
            R[u] = l - 1; X[u] = val;
            pending.push_back(u);
        }
        if (r < v)
        {
            R[r + 1] = v; X[r + 1] = val;
            pending.push_back(r + 1);
        }
    }
//    cout << "Finished\n";
    for (int it : deleted)
        se.erase(it);
    bit.update(x + 1, r - l + 1);
    for (int it : pending)
        se.insert(it);
//    cout << "After update:\n";
//    for (auto it : se)
//        cout << it[0] << ' ' << it[1] << ' ' << it[2] << '\n';
//    cout << "Count occurrences:\n";
//        for (int i = 0; i <= n; i++)
//            cout << i << " : " << bit.query(i + 1, i + 1) << '\n';
//        cout << "END\n"; cout << '\n' << '\n' << '\n';
}

void update_path(int u, int v, int x)
{
    while (tp[u] != tp[v])
    {
        if (d[tp[u]] < d[tp[v]])
            swap(u, v);
        update(pos[tp[u]], pos[u], x);
        u = par[tp[u]];
    }
    if (d[u] > d[v])
        swap(u, v);
    update(pos[u], pos[v], x);
}

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];

    DFS(1);
    DFS_HLD(1, 1);
    bit.update(1, n);
    se.insert(1);
    R[1] = n;
    for (int i = 1; i <= q; i++)
    {
        int l, r; cin >> l >> r;
        L[i] = l;
        queries[r].push_back(i);
    }

    for (int i = 1; i <= m; i++)
    {
        if (i != 1)
            update_path(c[i - 1], c[i], i - 1);
        update_path(c[i], c[i], i);

        for (int idx : queries[i])
            ans[idx] = bit.query(L[idx] + 1, m + 1);
    }

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

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: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 41