Submission #831978

#	Time	Username	Problem	Language	Result	Execution time	Memory
831978		NK_	Grapevine (NOI22_grapevine)	C++17	100 / 100	2053 ms	212332 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
 
// START OF SEGTREE
struct Seg {
	const ll ID = INFL, IDL = 0; ll comb(ll a, ll b) { return min(a, b); }
	int n; vl seg, lazy;
	void init(int N) {
		n = 1; while(n < N) n *= 2;
		seg.assign(2*n, ID); lazy.assign(2*n, IDL);
	}
 
	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); } 
 
	void push(int x, int L, int R) {
		seg[x] += lazy[x];
		if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x];
		lazy[x] = IDL;
	}
 
	void upd(int l, int r, ll v, int x, int L, int R) {
		push(x, L, R); if (r < L || R < l) return;
		if (l <= L && R <= r) {
			lazy[x] = v; push(x, L, R); return;
		}
		int M = (L + R) / 2;
		upd(l, r, v, 2*x, L, M);
		upd(l, r, v, 2*x+1, M+1, R);
		pull(x);
	}
 
	ll query(int l, int r, int x, int L, int R) {
		push(x, L, R); if (r < L || R < l) return 2 * ID;
		if (l <= L && R <= r) return seg[x];
		int M = (L + R) / 2;
		return comb(query(l, r, 2*x, L, M), query(l, r, 2*x+1, M+1, R));
	}
 
	void upd(int l, int r, ll v) { upd(l, r, v, 1, 0, n - 1); }
	ll query(int l, int r) { return query(l, r, 1, 0, n - 1); }
	ll query() { return seg[1]; }
};
// END OF SEGTREE
 
 
const int nax = 1e5 + 5;
 
// MAIN
vpi adj[nax]; int W[nax];
 
// CENTROID
vi chd[nax];
int sub[nax], proc[nax], siz[nax];
 
// CENTROID SUBTREES
vi eid[nax], st[nax], en[nax], par[nax]; 
Seg T[nax];
// __[u][t] = a property of the subtree rooted at u's t-th parent in the centroid tree
 
// START OF CENTROID
void gen(int u, int p = -1) {
	sub[u] = 1;
	for(auto& e : adj[u]) {
		int v, i; tie(v, i) = e;
		if (v != p && !proc[v]) {
			gen(v, u); sub[u] += sub[v];
		}
	}
}
 
int t = 0, C = -1;
void dfs(int u, int p = -1) {
	par[u].pb(C); st[u].pb(t++);
	for(auto& e : adj[u]) {
		int v, i; tie(v, i) = e;
		if (v != p && !proc[v]) {
			eid[v].pb(i);
			dfs(v, u);
		}
	}
	en[u].pb(t-1);
}
 
int find(int u, int n, int p = -1) {
	for(auto& e : adj[u]) {
		int v, i; tie(v, i) = e;
		if (v != p && !proc[v]) {
			if (2 * sub[v] > n) return find(v, n, u);
		}
	}
	return u;
}
 
int init(int u = 0) {
	gen(u); int c = find(u, sub[u]);
 
	t = 0, C = c; eid[c].pb(-1); dfs(c);
	proc[c] = 1;
 
	siz[c] = sub[u];
	assert(t <= 2 * siz[c]);
	T[c].init(2 * siz[c]);
 
	for(auto& e : adj[c]) {
		int v, i; tie(v, i) = e;
		if (!proc[v]) {
			int cv = init(v);
			chd[c].pb(cv);
		}
	}
 
	return c;
}
// END OF CENTROID
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q; cin >> N >> Q;
 
	unordered_map<ll, int> E;
	for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v >> W[i]; --u, --v;
		adj[u].pb(mp(v, i));
		adj[v].pb(mp(u, i));
		E[u * 1LL * N + v] = E[v * 1LL * N + u] = i;
	}
 
	int R = init();
 
	for(int u = 0; u < N; u++) {
		reverse(begin(par[u]), end(par[u]));
		reverse(begin(eid[u]), end(eid[u]));
		reverse(begin(st[u]), end(st[u]));
		reverse(begin(en[u]), end(en[u]));
	}
 
	for(int u = 0; u < N; u++) {
		int M = sz(par[u]);
		for(int p = 0; p < M; p++) {
			int e = eid[u][p], x = par[u][p];
			if (e != -1) {
				// cout << x << " " << u << endl;
				// cout << st[u][p] << " " << en[u][p] << " " << W[e] << endl;
				T[x].upd(st[u][p], en[u][p], W[e]);
			}
		}
	}
 
	// cout << endl;
	// cout << endl;
 
	for(int q = 0; q < Q; q++) {
		int type; cin >> type;
 
		if (type == 1) {
			int u; cin >> u; --u;
			
			ll ans = 2 * INFL;
 
			int M = sz(par[u]);
			for(int p = 0; p < M; p++) {
				int x = par[u][p], pos = st[u][p];
 
				ll dst = T[x].query(pos, pos);
				if (dst >= INFL) dst -= INFL;
 
				// cout << x << " TO " << u << ": " << dst << endl;
				// cout << x << " TO CLOSEST: " << T[x].query() << endl;
 
				ans = min(ans, dst + T[x].query());
			}
			cout << (ans >= INFL ? -1 : ans) << nl;
		}
 
		if (type == 2) {
			int u; cin >> u; --u;
			int M = sz(par[u]);
			for(int p = 0; p < M; p++) {
				int x = par[u][p];
				int pos = st[u][p];
 
				if (T[x].query(pos, pos) >= INFL) T[x].upd(pos, pos, -INFL);
				else T[x].upd(pos, pos, +INFL);
				// cout << u << " TO " << x << ": " << T[x].query(pos, pos) << endl;
			}
		}
 
		if (type == 3) {
			int u, v, w; cin >> u >> v >> w; --u, --v;
 
			int i = E[u * 1LL * N + v];
 
			for(int rep = 0; rep < 2; rep++) {
				int M = sz(par[u]);
				for(int p = 0; p < M; p++) {
					int x = par[u][p], e = eid[u][p];
					int l = st[u][p], r = en[u][p];
 
					if (e == i) T[x].upd(l, r, w - W[i]);
				}
 
				swap(u, v);
			}
 
			W[i] = w;
		}
 
	}
 
 
 
    return 0;
} 

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:157:6: warning: unused variable 'R' [-Wunused-variable]
  157 |  int R = init();
      |      ^

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