Submission #1256296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256296		PenguinsAreCute	Grapevine (NOI22_grapevine)	C++20	100 / 100	1368 ms	76184 KiB

Main

// the most daunting part is that this is task 4
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
namespace bribritt {
template<class dat, dat (*op)(dat, dat), dat (*e)(), class lazyT, dat (*app)(dat, lazyT), lazyT (*comb)(lazyT, lazyT), lazyT (*id)()>
struct lazyseg {
	private:
		int n, h;
		std::vector<dat> seg;
		std::vector<lazyT> lazy;
		void calc(int x) {seg[x] = app(op(seg[x<<1],seg[x<<1|1]),lazy[x]);}
		void apply(int x, lazyT v) {
			seg[x] = app(seg[x], v);
			if(x < n)
				lazy[x] = comb(lazy[x], v);
		}
		void build(int x) {
			for(x+=n;x>>=1;)
				calc(x);
		}
		void push(int x) {
			int s = h;
			for(x += n; s; s--) {
				int i = x >> s;
				apply(i<<1,lazy[i]);
				apply(i<<1|1,lazy[i]);
				lazy[i] = id();
			}
		}
	public:
		lazyseg(int _n): n(_n), h(32-__builtin_clz(n)), seg(2*_n, e()), lazy(n,id()) {}
		void set(int x, dat p) {
			push(x);
			seg[x+n] = p;
			build(x);
		}
		void update(int l, int r, lazyT v) {
			push(l);
			push(r++);
			int l0 = l, r0 = r;
			for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
				if(l&1)
					apply(l++,v);
				if(r&1)
					apply(--r,v);
			}
			build(l0);
			build(r0-1);
		}
		dat query(int l, int r) {
			push(l);
			push(r++);
			dat resl = e(), resr = e();
			for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
				if(l&1)
					resl = op(resl, seg[l++]);
				if(r&1)
					resr = op(seg[--r], resr);
			}
			return op(resl,resr);
		}
};
}
const long long INF = 2e14;
long long op(long long x, long long y) {return std::min(x, y);}
long long e() {return 2 * INF;}
long long app(long long x, long long lazy) {return x + lazy;}
long long comb(long long lazy1, long long lazy2) {return lazy1 + lazy2;}
long long id() {return 0;}
using segtree = bribritt::lazyseg<long long,op,e,long long,app,comb,id>;

const int MAXN = 121010;
const int MAXH = 18;
std::vector<std::pair<int,int>> adj[MAXN];
int sub[MAXN], centPar[MAXN], centLvl[MAXN];
int dfs0(int x, int p) {
	sub[x] = 1;
	for(auto [i, w]: adj[x])
		if(i != p && centLvl[i] == -1)
			sub[x] += dfs0(i, x);
	return sub[x];
}
int dfs1(int x, int p, int n) {
	for(auto [i, w]: adj[x])
		if(i != p && sub[i] > n/2 && centLvl[i] == -1)
			return dfs1(i, x, n);
	return x;
}
int counter[MAXH];
int pre[MAXH][MAXN], nd[MAXH][MAXN];
std::vector<segtree> seg(MAXH, segtree(MAXN));
void dfs2(int x, int p, int h) {
	pre[h][x] = counter[h]++;
	for(auto [i, w]: adj[x])
		if(i != p && centLvl[i] == -1) {
			dfs2(i, x, h);
			seg[h].update(pre[h][i],nd[h][i],w);
		}
	nd[h][x] = counter[h]-1;
}
void dfs3(int x, int p, int h) {
	int cent = dfs1(x, -1, dfs0(x, -1));
	dfs2(cent, -1, h);
	centLvl[cent] = h;
	centPar[cent] = p;
	for(auto [i, w]: adj[cent])
		if(centLvl[i] == -1)
			dfs3(i, cent, h + 1);
}
int main() {
	for(int i=0;i<MAXH;i++)
		seg[i].update(0,MAXN-1,-INF);
	int n, q;
	std::cin >> n >> q;
	for(int i=1,a,b,w;i<n;i++) {
		std::cin >> a >> b >> w;
		a--; b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	memset(centLvl, -1, sizeof(centLvl));
	dfs3(0, -1, 0);
	while(q--) {
		int a, b, w;
		std::cin >> a;
		if(a == 1) {
			std::cin >> a;
			a--;
			long long ans = INF;
			for(b=a;~b;b=centPar[b]) {
				long long distAB = seg[centLvl[b]].query(pre[centLvl[b]][a],pre[centLvl[b]][a]);
				if(distAB >= INF)
					distAB -= INF;
				long long distBGrape = seg[centLvl[b]].query(pre[centLvl[b]][b],nd[centLvl[b]][b]);
				ans = std::min(ans, distAB + distBGrape);
			}
			std::cout << (ans==INF?-1:ans) << "\n";
		} else if(a == 2) {
			std::cin >> a;
			a--;
			bool grape = (seg[centLvl[a]].query(pre[centLvl[a]][a],pre[centLvl[a]][a]) < INF);
			for(b=a;~b;b=centPar[b]) {
				seg[centLvl[b]].update(pre[centLvl[b]][a],pre[centLvl[b]][a],grape?INF:-INF);
			}
		} else {
			std::cin >> a >> b >> w;
			a--; b--;
			if(centLvl[a] > centLvl[b])
				std::swap(a, b);
			int origWeight = seg[centLvl[a]].query(pre[centLvl[a]][b],pre[centLvl[a]][b]) % INF;
			for(int c=a;~c;c=centPar[c]) {
				if(pre[centLvl[c]][a] > pre[centLvl[c]][b])
					std::swap(a, b);
				seg[centLvl[c]].update(pre[centLvl[c]][b], nd[centLvl[c]][b], w - origWeight);
			}
		}
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32