Submission #1279078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279078		Bui_Quoc_Cuong	Tourism (JOI23_tourism)	C++20	28 / 100	5093 ms	47708 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int B = 800;

int n, m, q;
vector <int> g[N];
int c[N];
int tin[N], tout[N], h[N], timedfs;
vector <int> hList, nList;
int rmq[N][30], lg[N];
set <pair <int, int>> set_euler;

struct Queries {
    int L, R, id;
    bool operator < (const Queries &x) const {
        if (L / B != x.L / B) return L < x.L;
        return ((L / B) & 1) ? R < x.R : R > x.R; 
    }
};

Queries Q[N];

int ans[N], res, l = 1, r, cnt[N];

void dfs (int u, int p) {
    tin[u] = ++ timedfs;
    nList.push_back(u);
    hList.push_back(h[u]);
    for (int &v : g[u]) {
        if (v == p) continue;
        h[v] = h[u] + 1;
        dfs (v, u);
        hList.push_back(h[u]);
        nList.push_back(u);
    }
    tout[u] = ++ timedfs;
}

int merge (int i, int j) {
    return hList[i] < hList[j] ? i : j;
}

int LCA (int u, int v) {
    if (tin[u] > tin[v]) swap (u, v);
    int k = lg[tin[v] - tin[u] + 1];
    return nList[merge(rmq[tin[u]][k], rmq[tin[v] - (1 << k) + 1][k])];
}

int dist (int u, int v) {
    return h[u] + h[v] - 2 * h[LCA(u, v)];
}

void add (int u) {
    cnt[tin[u]]++;
    if (cnt[tin[u]] >= 2) return;
    if (set_euler.empty()) {
        set_euler.insert(make_pair(tin[u], u));
        return;
    }   
    auto nxt = set_euler.lower_bound(make_pair(tin[u], 0));
    auto prv = nxt;
    if (nxt == set_euler.end()) {
        nxt = prev(nxt);
        prv = set_euler.begin();
    } else if (nxt == set_euler.begin()) {
        prv = set_euler.end();
        prv--;
    } else {
        prv = prev(nxt);
    }
    res-= dist (nxt -> second, prv -> second);
    res+= dist (nxt -> second, u);
    res+= dist (prv -> second, u);
    set_euler.insert(make_pair(tin[u], u));
}

void del (int u) {
    cnt[tin[u]]--;
    if (cnt[tin[u]] >= 1) return;
    if (set_euler.size() == 1) {
        set_euler.clear();
        return;
    }
    auto it = set_euler.lower_bound(make_pair(tin[u], u));
    auto prv = it, nxt = it;
    if (next(it) == set_euler.end()) {
        prv = prev(it);
        nxt = set_euler.begin();
    } else if (it == set_euler.begin()) {
        nxt = next(it);
        prv = prev(set_euler.end());
    } else {
        nxt = next(it);
        prv = prev(it);
    }
    res+= dist (nxt -> second, prv -> second);
    res-= dist (nxt -> second, u);
    res-= dist (prv -> second, u);
    set_euler.erase(make_pair(tin[u], u));
}   

void  MO (int id) {
    while (l > Q[id].L) {
        add (c[-- l]);
    }
    while (r < Q[id].R) {
        add (c[++ r]);
    }
    while (l < Q[id].L) {
        del (c[l ++]);
    }
    while (r > Q[id].R) {
        del (c[r --]);
    }
    ans[Q[id].id] = res;
}

void solve () {
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    for (int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    nList.push_back(0); hList.push_back(0);
    dfs(1, 1);

    int sz = nList.size();
    for (int i = 1; i <= sz; i++) {
        rmq[i][0] = i;
    }
    for (int j = 1; (1 << j) <= sz; j++) {
        for (int i = 1; i + (1 << j) - 1 <= sz; i++) {
            rmq[i][j] = merge(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 2; i <= sz; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    for (int i = 1; i <= q; i++) {
        cin >> Q[i].L >> Q[i].R;
        Q[i].id = i;
    }
    sort(Q + 1, Q + 1 + q);
    for (int i = 1; i <= q; i++) {
        MO(i);
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] / 2 + 1 << "\n";
    }
}           

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "kieuoanh"

    if (fopen(kieuoanh".inp", "r")) {
        freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
    }

    solve();

    return 0;
}

Compilation message (stderr)

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