Submission #1117222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117222		hqminhuwu	Tourism (JOI23_tourism)	C++14	100 / 100	773 ms	46492 KiB

tourism

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 5e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

int n, m, bit[N], pos[N], head[N], sz[N], hv[N], u, v, q, cnt, dep[N], c[N], p[N];
vector <int> a[N];
vector <pii> qq[N];

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

int get (int i){
    int res = 0;
    for (; i; i -= i & -i)
        res += bit[i];
    return res;
}

void dfsz (int u){
    sz[u] = 1;
    for (int v : a[u]){
        if (sz[v]) continue;
        dep[v] = dep[u] + 1;
        p[v] = u;
        dfsz(v);
        sz[u] += sz[v];
        if (sz[v] > sz[hv[u]]){
            hv[u] = v;
        }
    }
}

void dcp (int u, int h){
    head[u] = h;
    pos[u] = ++cnt;
    
    if (hv[u]){
        dcp(hv[u], h);
    }

    for (int v : a[u]){
        if (sz[v] > sz[u] || v == hv[u]) continue;
        dcp(v, v);
    }
}

set <piii> s;

void uwu (int l, int r, int val){
	auto it = s.lower_bound({l, {l, 0}});
	
    if(it != s.begin()) it--;
	vector <piii> rem, add;
    add.pb({l, {r, val}});

	for (; it != s.end() && (*it).st <= r; ++it){
		int fl = (*it).st, fr = (*it).nd.st, fv = (*it).nd.nd;
		if(fr < l) continue;
		rem.pb(*it);
		if(fl < l) add.pb({fl, {l - 1, fv}});
		if(fr > r) add.pb({r + 1, {fr, fv}});
	}

	for (piii x : rem){
		upd(x.nd.nd, -(x.nd.st - x.st + 1));
		s.erase(x);
	}

	for(piii x : add){
		upd(x.nd.nd, x.nd.st - x.st + 1);
		s.insert(x);
	}
}

void owo (int u, int v, int val){
    for (; head[u] != head[v]; v = p[head[v]]){
        if (dep[head[u]] > dep[head[v]])
            swap(u, v);
        uwu(pos[head[v]], pos[v], val);
    }
    if (dep[u] > dep[v])
        swap(u, v);
    uwu(pos[u], pos[v], val);
}


int ans[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> m >> q;

    forf (i, 1, n){
        cin >> u >> v;
        a[u].pb(v);
        a[v].pb(u);
    }

    dfsz(1);
    dcp(1, 1);

    forr (i, 1, m){
        cin >> c[i];
    }

    forr (i, 1, q){
        cin >> u >> v;
        qq[v].pb({u, i});
    }    

    forr (i, 1, m){
        if (i > 1){
            owo(c[i], c[i - 1], i);
        }

        for (pii t : qq[i]){
            if (t.st == i){
                ans[t.nd] = 1;
            } else {
                ans[t.nd] = get(i) - get(t.st);
            }
        }
    }

    forr (i, 1, q){
        cout << ans[i] << "\n";
    }


    

    return 0;
}
/*



*/

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