Submission #799872

#	Time	Username	Problem	Language	Result	Execution time	Memory
799872		phoenix	Tourism (JOI23_tourism)	C++17	100 / 100	480 ms	24992 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100000 + 10;
const int M = (1 << 17);

int n, m, q;

int T;
int sz[N];
int tin[N];
int tout[N];
int depth[N];
int par[N];
int head[N];
int heavy[N];
vector<int> g[N];
int sum_cnt[2 * M];
bool have[2 * M];
int color[2 * M];

void upd(int pos, int d) {
    for (sum_cnt[pos += M] += d; pos > 1; pos >>= 1)
        sum_cnt[pos >> 1] = sum_cnt[pos] + sum_cnt[pos ^ 1];
}
int get(int ql, int qr) {
    int res = 0;
    for (ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if (ql & 1)
            res += sum_cnt[ql++];
        if (qr & 1)
            res += sum_cnt[--qr];
    }
    return res;
}
void precalc(int s, int p = 0) {
    sz[s] = 1;
    par[s] = p;
    depth[s] = depth[p] + (p > 0);
    for (int &to : g[s]) {
        if (to == p)
            continue;
        precalc(to, s);
        sz[s] += sz[to];
        if (sz[heavy[s]] < sz[to])
            heavy[s] = to;
    }
}

void decompose(int s, int h) {
    tin[s] = T++;
    head[s] = h;
    if(heavy[s]) decompose(heavy[s], h);
    for(int to : g[s]) {
        if(to == par[s] || to == heavy[s]) continue;
        decompose(to, to);
    }
    tout[s] = T;
}
void recalc(int v) {
    have[v] = (color[v] > 0);
    if(2 * v < 2 * M && have[2 * v]) have[v] = true;
    if(2 * v + 1 < 2 * M && have[2 * v + 1]) have[v] = true;
}
void push(int v) {
    if(!color[v] || v >= M) return;
    color[2 * v] = color[v];
    recalc(2 * v);
    color[2 * v + 1] = color[v];
    recalc(2 * v + 1);
    color[v] = 0;
}   
void set_color(int v, int d, int cl) {
    if(color[v])
        upd(color[v], -d);
    color[v] = cl;
    if(color[v])
        upd(color[v], d);
    recalc(v);
} 
void clear(int l, int r, int v) {
    set_color(v, r - l + 1, 0);
    if(!have[v]) return;
    int mid = (l + r) / 2;
    clear(l, mid, 2 * v);
    clear(mid + 1, r, 2 * v + 1);
    have[v] = false;
}
void update(int ql, int qr, int cl, int l, int r, int v, bool type = 0) {
    if(qr < l || ql > r) return;
    if(ql <= l && r <= qr) {
        clear(l, r, v);
        set_color(v, r - l + 1, cl); 
        return;
    }
    push(v);
    int mid = (l + r) / 2;
    update(ql, qr, cl, l, mid, 2 * v, 0);
    update(ql, qr, cl, mid + 1, r, 2 * v + 1, 0);
    recalc(v);
}
void update(int u, int v, int cl) {
    for(; head[u] != head[v]; v = par[head[v]]) {
        if(depth[head[u]] > depth[head[v]]) swap(u, v);
        update(tin[head[v]], tin[v], cl, 0, M - 1, 1);
    }
    if(depth[u] > depth[v]) swap(u, v);
    update(tin[u], tin[v], cl, 0, M - 1, 1);
}

struct query {
    int l, r, i;
};

vector<query> qr[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int c[m + 1];
    for(int i = 1; i <= m; i++) 
        cin >> c[i];
    
    precalc(1);
    decompose(1, 1);
    // for(int i = 1; i <= n; i++) {
    //     cout << '{' << head[i] << ' ' << tin[i] << '}' << ' ';
    // }
    // cout << '\n';
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qr[r].push_back({l, r, i});
    }
    int res[q] = {};
    for(int i = 1; i <= m; i++) {
        if(i > 1) 
            update(c[i], c[i - 1], i - 1);
        for(auto t : qr[i]) {
            if(t.l == t.r) res[t.i] = 1;
            else res[t.i] = get(t.l, t.r);
        }
        // for(int x = 1; x <= m; x++) 
        //     cout << get(x, x) << ' ';
        // cout << '\n';
    }
    for(int i = 0; i < q; i++) 
        cout << res[i] << '\n';
}

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