Submission #886621

#	Time	Username	Problem	Language	Result	Execution time	Memory
886621		vjudge1	Grapevine (NOI22_grapevine)	C++17	0 / 100	223 ms	50004 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second 
#define N 300005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int INF = 2e18 + 7;


int edge[N], ind[N], tin[N], tout[N], rev[N], dist[N], cntr = 1;
vector<pii> adj[N];
int tree[2][4 * N], lazy[4 * N];


void push(int node, int l, int r){
	tree[0][node] += lazy[node];
	tree[1][node] += lazy[node];
	if (l != r){
		lazy[L(node)] += lazy[node];
		lazy[R(node)] += lazy[node];
	}
	lazy[node] = 0;
}

void update(int node, int l, int r, int sl, int sr, int val){
	push(node, l, r);
	if (l > sr || r < sl) return;
	if (l >= sl && r <= sr){
		lazy[node] += val;
		push(node, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update(L(node), l, mid, sl, sr, val);
	update(R(node), mid + 1, r, sl, sr, val);
	for (int i = 0; i < 2; i++)
		tree[i][node] = min(tree[i][L(node)], tree[i][R(node)]);
}


void build(int node, int l, int r){
	if (l == r){
		tree[0][node] = dist[rev[l]];
		tree[1][node] = INF;
		return;
	}
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
	for (int i = 0; i < 2; i++)
		tree[i][node] = min(tree[i][L(node)], tree[i][R(node)]);
}

void sett(int node, int l, int r, int sl){
	push(node, l, r);
	if (l > sl || r < sl) return;
	if (l == r){
		if (tree[1][node] >= INF) tree[1][node] = tree[0][node];
		else tree[1][node] = INF;
		return;
	}
	int mid = (l + r) / 2;
	sett(L(node), l, mid, sl);
	sett(R(node), mid + 1, r, sl);
	for (int i = 0; i < 2; i++)
		tree[i][node] = min(tree[i][L(node)], tree[i][R(node)]);
}

int query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > sr || r < sl) return INF;
	if (l >= sl && r <= sr) return tree[1][node];
	int mid = (l + r) / 2;
	return min(query(L(node), l, mid, sl, sr), query(R(node), mid + 1, r, sl, sr));
}

void dfs(int node, int root, int d){
	tin[node] = ind[node] = cntr;
	rev[cntr] = node;
	dist[node] = d;
	cntr++;
	for (auto i : adj[node]){
		int curr = i.st, w = edge[i.nd];
		if (curr != root) dfs(curr, node, d + w);
	}
	tout[node] = cntr;
}


int32_t main(){
	//fileio();
	fastio();

	int n, q;
	cin>>n>>q;
	map<pii, int> e;
	for (int i = 1; i < n; i++){
		int u, v, w;
		cin>>u>>v>>w;
		adj[u].pb({v, i});
		adj[v].pb({u, i});
		e[{u, v}] = e[{v, u}] = i;
		edge[i] = w;
	}

	dfs(1, 0, 0);
	build(1, 1, n);
	set<int> grape;
	while(q--){
		int t;
		cin>>t;
		if (t == 1){
			int x;
			cin>>x;
			int ans = query(1, 1, n, 1, n);
			if (ans < INF) cout<<ans<<endl;
			else cout<<-1<<endl;
		}
		else if (t == 2){
			int x;
			cin>>x;
			sett(1, 1, n, ind[x]);
		}
		else{
			int a, b, w;
			cin>>a>>b>>w;
			int ee = e[{a, b}];
			int diff = w - edge[ee];
			edge[ee] = w;
			if (tin[a] > tin[b]) swap(a, b);
			update(1, 1, n, tin[b], tout[b] - 1, diff);
		}
	}

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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