Submission #849296

#	Time	Username	Problem	Language	Result	Execution time	Memory
849296		He_Huanglu	Tourism (JOI23_tourism)	C++17	100 / 100	294 ms	118240 KiB

tourism

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 1e5 + 5, S = 18;
int n, m, q, timer;
int d[N], heavy[N], chain[N], sz[N], par[N], num[N], ans[N], sp[2 * N][S], g[N][S], c[N], bit[N], f[N], Left[N];
vector <int> ke[N], euler, A, val[N], lis[N];
stack <int> st[N];

void dfs(int u, int pre = 0) {
    int mx = 0;
    sz[u] = 1; heavy[u] = -1; num[u] = timer++;
    euler.push_back(u);
    A.push_back(d[u]);
    for(int v : ke[u]) if(v != pre) {
        sz[u] += sz[v];
        par[v] = u; d[v] = d[u] + 1;
        dfs(v, u);
        euler.push_back(u);
        A.push_back(d[u]);
        timer++;
        if(sz[v] > mx) {
            mx = sz[v];
            heavy[u] = v;
        }
    }
}

void dfss(int u, int pre = 0) {
    if(u == 1) f[u] = chain[u] = 1;
    for(int v : ke[u]) if(v != pre) {
        if(v == heavy[u]) {
            chain[v] = chain[u];
            f[v] = f[u] + 1;
        }
        else chain[v] = v, f[v] = 1;
        dfss(v, u);
    }
}

void upd(int x, int v) {
    for(; x <= m; x += (x & -x)) bit[x] += v;
}

void upds(int l, int r, int v) {
    upd(l, v);
    upd(r + 1, -v);
}

int get(int x) {
    int ret = 0;
    for(; x > 0; x -= (x & -x)) ret += bit[x];
    return ret;
}

void solve(int p, int v, int i) {
    upds(st[p].top() + 1, i, v);
    while (val[p].size() && v > val[p].back()) {
        int r = st[p].top(); st[p].pop();
        upds(st[p].top() + 1, r, v - val[p].back());
        val[p].pop_back();
    }
    st[p].push(i);
    val[p].push_back(v);
}

void jump(int i, int u) {
    while (u) {
        solve(chain[u], f[u], i);
        u = par[chain[u]];
    }
}

void init(int n) {
    for(int i = 0; i < n; i++) sp[i][0] = i;
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i + (1 << j) - 1 < n; i++) {
            int o = i + (1 << j - 1);
            if(A[sp[i][j - 1]] < A[sp[o][j - 1]]) {
                sp[i][j] = sp[i][j - 1];
            }
            else sp[i][j] = sp[o][j - 1];
        }
    }
}

int lca(int u, int v) {
    int l = min(num[u], num[v]), r = max(num[u], num[v]);
    int k = log2(r - l + 1);
    int i = sp[l][k], j = sp[r - (1 << k) + 1][k];
    return (A[i] < A[j]) ? euler[i] : euler[j];
}

void build() {
    for(int i = 1; i <= m; i++) g[i][0] = c[i];
    for(int j = 1; (1 << j) <= m; j++) {
        for(int i = 1; i + (1 << j) - 1 <= m; i++) {
            g[i][j] = lca(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
        }
    }
}

int get(int l, int r) {
    int k = log2(r - l + 1);
    return lca(g[l][k], g[r - (1 << k) + 1][k]);
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) st[i].push(0);
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    for(int i = 1; i <= m; i++) cin >> c[i];
    for(int i = 1; i <= q; i++) {
        int r; cin >> Left[i] >> r;
        lis[r].push_back(i);
    }
    dfs(1);
    dfss(1);
    init(timer);
    build();
    for(int i = 1; i <= m; i++) {
        jump(i, c[i]);
        for(int j : lis[i]) ans[j] = get(Left[j]) - d[(get(Left[j], i))];
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

tourism.cpp: In function 'void init(int)':
tourism.cpp:81:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   81 |             int o = i + (1 << j - 1);
      |                               ~~^~~
tourism.cpp: In function 'void build()':
tourism.cpp:101:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  101 |             g[i][j] = lca(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
      |                                                    ~~^~~
tourism.cpp: At global scope:
tourism.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main () {
      | ^~~~
tourism.cpp: In function 'int main()':
tourism.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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