Submission #796622

#	Time	Username	Problem	Language	Result	Execution time	Memory
796622		vjudge1	Tourism (JOI23_tourism)	C++17	0 / 100	2 ms	2772 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], head[s]);
    for(int to : g[s]) {
        if(to == par[s] || to == heavy[s]) continue;
        decompose(to, to);
    }
    tout[s] = T;
}
void push(int v) {
    if(!color[v] || v >= M) return;
    color[2 * v] = color[v];
    color[2 * v + 1] = color[v];
    color[v] = 0;
}   
void set_color(int v, int l, int r, int cl) {
    if(color[v])
        upd(color[v], -r + l - 1);
    color[v] = cl;
    if(color[v])
        upd(color[v], r - l + 1);
} 
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) {
        if(!type) 
            set_color(v, l, r, cl);
        else {
            if(!have[v]) return;
            set_color(v, l, r, 0);
        }
        int mid = (l + r) / 2; 
        update(ql, qr, cl, l, mid, 2 * v, 1);
        update(ql, qr, cl, mid + 1, r, 2 * v + 1, 1);
        have[v] = ((color[v] > 0) | have[2 * v] | have[2 * v + 1]);
        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);
    have[v] = ((color[v] > 0) | have[2 * v] | have[2 * v + 1]);
}
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;
};

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';
    vector<query> v;
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        v.push_back({l, r, i});
    }
    int res[q] = {};
    sort(v.begin(), v.end(), [](query a, query b) {return a.r < b.r;});
    int lb = 0;
    for(int i = 1; i <= m; i++) {
        if(i > 1) 
            update(c[i], c[i - 1], i - 1);
        while(lb < q && v[lb].r < i) lb++;
        while(lb < q && v[lb].r == i) {
            if(v[lb].l == v[lb].r) res[v[lb].i] = 1;
            else res[v[lb].i] = get(v[lb].l, M - 1);
            lb++;
        }
        // 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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41