제출 #1169755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169755		daoquanglinh2007	Grapevine (NOI22_grapevine)	C++20	100 / 100	1277 ms	242612 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 1e5;
const ll inf = 1e18, LIM = 1e16;

struct node{
	ll d, res;
};

int n, q, sz[NM+5], num[NM+5], parent_cen[NM+5], timer;
bool del[NM+5];
vector <pii> adj[NM+5];
vector <int> vlist[NM+5], tin[NM+5], tout[NM+5], tour[NM+5], f[NM+5];
vector <ll> d[NM+5], lazy[NM+5];
vector <node> st[NM+5];
vector <int> tmp;
map <pii, int> len;

void dfs_sz(int u, int p){
	sz[u] = 1;
	tmp.push_back(u);
	for (pii _ : adj[u]){
		int v = _.fi;
		if (v == p || del[v]) continue;
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
}

int dfs_fc(int rt, int u, int p){
	for (pii _ : adj[u]){
		int v = _.fi;
		if (v == p || del[v]) continue;
		if (sz[v] > sz[rt]/2) return dfs_fc(rt, v, u);
	}
	return u;
}

void dfs_dp(int rt, int u, int p, int pos_u){
	tin[rt][pos_u] = timer++;
	tour[rt][timer-1] = pos_u;
	for (pii _ : adj[u]){
		int v = _.fi, w = _.se;
		if (v == p || del[v]) continue;
		int pos_v = lower_bound(vlist[rt].begin(), vlist[rt].end(), v)-vlist[rt].begin();
		d[rt][pos_v] = d[rt][pos_u]+w;
		if (u == rt) f[rt][pos_v] = pos_v;
		else f[rt][pos_v] = f[rt][pos_u];
		dfs_dp(rt, v, u, pos_v);
	}
	tout[rt][pos_u] = timer-1;
}

void build(int rt, int id, int l, int r){
	st[rt][id].res = +inf;
	if (l == r){
		st[rt][id].d = d[rt][tour[rt][l]];
		return;
	}
	int mid = (l+r)/2;
	build(rt, 2*id, l, mid);
	build(rt, 2*id+1, mid+1, r);
}

void decompose(int u, int p){
	tmp.clear();
	dfs_sz(u, -1);
	sort(tmp.begin(), tmp.end());
	u = dfs_fc(u, u, -1);
	parent_cen[u] = p;
	del[u] = 1;
	
	vlist[u] = tmp;
	num[u] = isz(vlist[u]);
	
	tin[u].resize(num[u]);
	tout[u].resize(num[u]);
	tour[u].resize(num[u]);
	f[u].resize(num[u]);
	d[u].resize(num[u]);
	
	timer = 0;
	dfs_dp(u, u, -1, lower_bound(vlist[u].begin(), vlist[u].end(), u)-vlist[u].begin());
	
	st[u].resize(4*num[u]+1);
	build(u, 1, 0, num[u]-1);
	lazy[u].assign(4*num[u]+1, 0);
	
	for (pii _ : adj[u]){
		int v = _.fi;
		if (del[v]) continue;
		decompose(v, u);
	}
}

void down(int rt, int id, int l, int r){
	int mid = (l+r)/2;
	if (l == mid) st[rt][2*id].d += lazy[rt][id];
	if (mid+1 == r) st[rt][2*id+1].d += lazy[rt][id];
	st[rt][2*id].res += lazy[rt][id];
	st[rt][2*id+1].res += lazy[rt][id];
	lazy[rt][2*id] += lazy[rt][id];
	lazy[rt][2*id+1] += lazy[rt][id];
	lazy[rt][id] = 0;
}

void p_update(int rt, int id, int l, int r, int i){
	if (i < l || i > r) return;
	if (l == r){
		if (st[rt][id].res > LIM) st[rt][id].res = st[rt][id].d;
		else st[rt][id].res = +inf;
		return;
	}
	down(rt, id, l, r);
	int mid = (l+r)/2;
	p_update(rt, 2*id, l, mid, i);
	p_update(rt, 2*id+1, mid+1, r, i);
	st[rt][id].res = min(st[rt][2*id].res, st[rt][2*id+1].res);
}

void add(int rt, int id, int l, int r, int u, int v, int val){
	if (u > v || v < l || u > r) return;
	if (l >= u && r <= v){
		if (l == r) st[rt][id].d += val;
		st[rt][id].res += val;
		lazy[rt][id] += val;
		return;
	}
	down(rt, id, l, r);
	int mid = (l+r)/2;
	add(rt, 2*id, l, mid, u, v, val);
	add(rt, 2*id+1, mid+1, r, u, v, val);
	st[rt][id].res = min(st[rt][2*id].res, st[rt][2*id+1].res);
}

ll get(int rt, int id, int l, int r, int u, int v){
	if (u > v || v < l || u > r) return +inf;
	if (l >= u && r <= v) return st[rt][id].res;
	down(rt, id, l, r);
	int mid = (l+r)/2;
	return min(get(rt, 2*id, l, mid, u, v), get(rt, 2*id+1, mid+1, r, u, v));
}

ll get_d(int rt, int id, int l, int r, int i){
	if (l == r) return st[rt][id].d;
	down(rt, id, l, r);
	int mid = (l+r)/2;
	if (i <= mid) return get_d(rt, 2*id, l, mid, i);
	return get_d(rt, 2*id+1, mid+1, r, i);
}

ll query(int rt, int u){
	if (rt == u) return st[rt][1].res;
	int pos_u = lower_bound(vlist[rt].begin(), vlist[rt].end(), u)-vlist[rt].begin();
	return min(get(rt, 1, 0, num[rt]-1, 0, tin[rt][f[rt][pos_u]]-1), get(rt, 1, 0, num[rt]-1, tout[rt][f[rt][pos_u]]+1, num[rt]-1))
	      +get_d(rt, 1, 0, num[rt]-1, tin[rt][pos_u]);
}

void soak(int rt, int u){
	int pos_u = lower_bound(vlist[rt].begin(), vlist[rt].end(), u)-vlist[rt].begin();
	p_update(rt, 1, 0, num[rt]-1, tin[rt][pos_u]);
}

void add(int rt, int u, int v, int val){
	int pos_u = lower_bound(vlist[rt].begin(), vlist[rt].end(), u)-vlist[rt].begin();
	int pos_v = lower_bound(vlist[rt].begin(), vlist[rt].end(), v)-vlist[rt].begin();
	
	if (tin[rt][pos_u] < tin[rt][pos_v]){
		add(rt, 1, 0, num[rt]-1, tin[rt][pos_v], tout[rt][pos_v], val);
	}
	else{
		add(rt, 1, 0, num[rt]-1, tin[rt][pos_u], tout[rt][pos_u], val);
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> q;
	for (int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		len[mp(u, v)] = len[mp(v, u)] = w;
		adj[u].push_back(mp(v, w));
		adj[v].push_back(mp(u, w));
	}
	decompose(1, -1);
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int u; cin >> u;
			ll ans = +inf;
			for (int rt = u; rt != -1; rt = parent_cen[rt]){
				ans = min(ans, query(rt, u));
			}
			if (ans > LIM) cout << "-1\n";
			else cout << ans << '\n';
		}
		else if (type == 2){
			int u; cin >> u;
			for (int rt = u; rt != -1; rt = parent_cen[rt])
				soak(rt, u);
		}
		else{
			int u, v, w;
			cin >> u >> v >> w;
			int pre = len[mp(u, v)];
			if (num[u] < num[v]) swap(u, v);
			for (int rt = u; rt != -1; rt = parent_cen[rt])
				add(rt, u, v, w-pre);
			len[mp(u, v)] = len[mp(v, u)] = w;
		}
	}
	return 0;
}

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