oj.uz

Submission #886624

# Submission time Handle Problem Language Result Execution time Memory
886624 2023-12-12T12:38:38 Z vjudge1 Grapevine (NOI22_grapevine) C++17
14 / 100
 250 ms 58752 KB 
#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], mark[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 (mark[l] == 0) tree[1][node] = tree[0][node], mark[l] = 1;
		else tree[1][node] = INF, mark[l] = 0;
		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;
	int cnt = 0;
	while(q--){
		int t;
		cin>>t;
		if (t == 1){
			int x;
			cin>>x;
			int ans = query(1, 1, n, 1, n);
			if (cnt > 0) cout<<ans<<endl;
			else cout<<-1<<endl;
		}
		else if (t == 2){
			int x;
			cin>>x;
			if (mark[ind[x]]) cnt--;
			else cnt++;
			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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 27484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 53560 KB Output is correct
2 Correct 224 ms 56680 KB Output is correct
3 Correct 250 ms 56404 KB Output is correct
4 Correct 127 ms 58740 KB Output is correct
5 Correct 139 ms 57108 KB Output is correct
6 Correct 129 ms 57680 KB Output is correct
7 Correct 138 ms 55360 KB Output is correct
8 Correct 119 ms 54976 KB Output is correct
9 Correct 131 ms 54976 KB Output is correct
10 Correct 127 ms 58076 KB Output is correct
11 Correct 123 ms 58752 KB Output is correct
12 Correct 136 ms 57400 KB Output is correct
13 Correct 117 ms 54984 KB Output is correct
14 Correct 123 ms 54972 KB Output is correct
15 Correct 139 ms 55324 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 53588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 53244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 53764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 27484 KB Output isn't correct
2 Halted 0 ms 0 KB -