oj.uz

Submission #831932

# Submission time Handle Problem Language Result Execution time Memory
831932 2023-08-20T17:56:49 Z NK_ Grapevine (NOI22_grapevine) C++17
68 / 100
 1826 ms 1048576 KB 
// 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
int sub[nax], proc[nax], siz[nax];

// CENTROID SUBTREES
const int LG = 17;
int eid[nax][LG], st[nax][LG], en[nax][LG], par[nax][LG];
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;
int LVL = 0;
void dfs(int u, int p = -1) {
	par[u][LVL] = C; st[u][LVL] = t++;
	for(auto& e : adj[u]) {
		int v, i; tie(v, i) = e;
		if (v != p && !proc[v]) {
			eid[v][LVL] = i;
			dfs(v, u); sub[u] += sub[v];
		}
	}
	en[u][LVL] = 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][LVL] = -1; dfs(c);
	proc[c] = 1;

	siz[c] = sub[u];
	assert(t <= siz[c]);
	T[c].init(siz[c]);

	for(auto& e : adj[c]) {
		int v, i; tie(v, i) = e;
		if (!proc[v]) {
			++LVL; init(v); --LVL;
		}
	}

	return c;
}
// END OF CENTROID

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	memset(par, -1, sizeof(par));

	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++) {
		for(int p = 0; p < LG; p++) {
			int e = eid[u][p], x = par[u][p]; if (x == -1) continue;
			if (e != -1) T[x].upd(st[u][p], en[u][p], W[e]);
		}
	}

	for(int q = 0; q < Q; q++) {
		int type; cin >> type;

		if (type == 1) {
			int u; cin >> u; --u;
			
			ll ans = 2 * INFL;

			for(int p = 0; p < LG; p++) {
				int x = par[u][p], pos = st[u][p]; 
 				if (x == -1) continue;

				ll dst = T[x].query(pos, pos);
				if (dst >= INFL) dst -= INFL;

				ans = min(ans, dst + T[x].query());
			}
			cout << (ans >= INFL ? -1 : ans) << nl;
		}

		if (type == 2) {
			int u; cin >> u; --u;
			for(int p = 0; p < LG; p++) {
				int x = par[u][p], pos = st[u][p]; 
 				if (x == -1) continue;

				if (T[x].query(pos, pos) >= INFL) T[x].upd(pos, pos, -INFL);
				else T[x].upd(pos, pos, +INFL);
			}
		}

		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++) {
				for(int p = 0; p < LG; p++) {
					int x = par[u][p], e = eid[u][p]; if (x == -1) continue;

					if (e == i) T[x].upd(st[u][p], en[u][p], w - W[i]);
				}

				swap(u, v);
			}

			W[i] = w;
		}

	}



    return 0;
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17876 KB Output is correct
2 Correct 13 ms 17900 KB Output is correct
3 Correct 13 ms 17984 KB Output is correct
4 Correct 13 ms 17924 KB Output is correct
5 Correct 13 ms 17916 KB Output is correct
6 Correct 16 ms 17888 KB Output is correct
7 Correct 9 ms 17304 KB Output is correct
8 Correct 10 ms 17272 KB Output is correct
9 Correct 12 ms 17344 KB Output is correct
10 Correct 14 ms 17876 KB Output is correct
11 Correct 15 ms 17876 KB Output is correct
12 Correct 14 ms 17984 KB Output is correct
13 Correct 12 ms 17236 KB Output is correct
14 Correct 8 ms 17236 KB Output is correct
15 Correct 12 ms 17344 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1271 ms 115064 KB Output is correct
2 Correct 1240 ms 116368 KB Output is correct
3 Correct 1340 ms 115400 KB Output is correct
4 Correct 1070 ms 123904 KB Output is correct
5 Correct 1045 ms 116496 KB Output is correct
6 Correct 1052 ms 118872 KB Output is correct
7 Correct 266 ms 65004 KB Output is correct
8 Correct 171 ms 64044 KB Output is correct
9 Correct 174 ms 64120 KB Output is correct
10 Correct 1066 ms 120888 KB Output is correct
11 Correct 1000 ms 119520 KB Output is correct
12 Correct 1022 ms 122416 KB Output is correct
13 Correct 172 ms 64236 KB Output is correct
14 Correct 224 ms 64232 KB Output is correct
15 Correct 178 ms 64712 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1497 ms 525744 KB Output is correct
2 Correct 1514 ms 527764 KB Output is correct
3 Correct 1643 ms 529000 KB Output is correct
4 Correct 1476 ms 505304 KB Output is correct
5 Correct 1826 ms 507088 KB Output is correct
6 Correct 1567 ms 504076 KB Output is correct
7 Correct 1382 ms 502872 KB Output is correct
8 Correct 1717 ms 524692 KB Output is correct
9 Correct 1516 ms 504384 KB Output is correct
10 Correct 1507 ms 527912 KB Output is correct
11 Correct 1553 ms 505868 KB Output is correct
12 Correct 1535 ms 502156 KB Output is correct
13 Correct 1501 ms 526300 KB Output is correct
14 Correct 1484 ms 502204 KB Output is correct
15 Correct 1504 ms 507396 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1386 ms 126720 KB Output is correct
2 Correct 1426 ms 130884 KB Output is correct
3 Correct 1308 ms 114384 KB Output is correct
4 Correct 1142 ms 125688 KB Output is correct
5 Correct 1140 ms 121628 KB Output is correct
6 Correct 1153 ms 123048 KB Output is correct
7 Correct 193 ms 65616 KB Output is correct
8 Correct 200 ms 66544 KB Output is correct
9 Correct 200 ms 65760 KB Output is correct
10 Correct 1129 ms 138424 KB Output is correct
11 Correct 1048 ms 119656 KB Output is correct
12 Correct 1090 ms 123556 KB Output is correct
13 Correct 197 ms 65388 KB Output is correct
14 Correct 201 ms 66652 KB Output is correct
15 Correct 205 ms 65892 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1397 ms 124760 KB Output is correct
2 Correct 1387 ms 126884 KB Output is correct
3 Correct 1356 ms 120664 KB Output is correct
4 Correct 1099 ms 126944 KB Output is correct
5 Correct 1127 ms 126236 KB Output is correct
6 Correct 1161 ms 123076 KB Output is correct
7 Correct 227 ms 65520 KB Output is correct
8 Correct 214 ms 66148 KB Output is correct
9 Correct 197 ms 66312 KB Output is correct
10 Correct 1093 ms 117212 KB Output is correct
11 Correct 1148 ms 120804 KB Output is correct
12 Correct 1107 ms 132176 KB Output is correct
13 Correct 193 ms 66192 KB Output is correct
14 Correct 202 ms 65624 KB Output is correct
15 Correct 197 ms 65600 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17876 KB Output is correct
2 Correct 13 ms 17900 KB Output is correct
3 Correct 13 ms 17984 KB Output is correct
4 Correct 13 ms 17924 KB Output is correct
5 Correct 13 ms 17916 KB Output is correct
6 Correct 16 ms 17888 KB Output is correct
7 Correct 9 ms 17304 KB Output is correct
8 Correct 10 ms 17272 KB Output is correct
9 Correct 12 ms 17344 KB Output is correct
10 Correct 14 ms 17876 KB Output is correct
11 Correct 15 ms 17876 KB Output is correct
12 Correct 14 ms 17984 KB Output is correct
13 Correct 12 ms 17236 KB Output is correct
14 Correct 8 ms 17236 KB Output is correct
15 Correct 12 ms 17344 KB Output is correct
16 Correct 1271 ms 115064 KB Output is correct
17 Correct 1240 ms 116368 KB Output is correct
18 Correct 1340 ms 115400 KB Output is correct
19 Correct 1070 ms 123904 KB Output is correct
20 Correct 1045 ms 116496 KB Output is correct
21 Correct 1052 ms 118872 KB Output is correct
22 Correct 266 ms 65004 KB Output is correct
23 Correct 171 ms 64044 KB Output is correct
24 Correct 174 ms 64120 KB Output is correct
25 Correct 1066 ms 120888 KB Output is correct
26 Correct 1000 ms 119520 KB Output is correct
27 Correct 1022 ms 122416 KB Output is correct
28 Correct 172 ms 64236 KB Output is correct
29 Correct 224 ms 64232 KB Output is correct
30 Correct 178 ms 64712 KB Output is correct
31 Correct 1497 ms 525744 KB Output is correct
32 Correct 1514 ms 527764 KB Output is correct
33 Correct 1643 ms 529000 KB Output is correct
34 Correct 1476 ms 505304 KB Output is correct
35 Correct 1826 ms 507088 KB Output is correct
36 Correct 1567 ms 504076 KB Output is correct
37 Correct 1382 ms 502872 KB Output is correct
38 Correct 1717 ms 524692 KB Output is correct
39 Correct 1516 ms 504384 KB Output is correct
40 Correct 1507 ms 527912 KB Output is correct
41 Correct 1553 ms 505868 KB Output is correct
42 Correct 1535 ms 502156 KB Output is correct
43 Correct 1501 ms 526300 KB Output is correct
44 Correct 1484 ms 502204 KB Output is correct
45 Correct 1504 ms 507396 KB Output is correct
46 Correct 1386 ms 126720 KB Output is correct
47 Correct 1426 ms 130884 KB Output is correct
48 Correct 1308 ms 114384 KB Output is correct
49 Correct 1142 ms 125688 KB Output is correct
50 Correct 1140 ms 121628 KB Output is correct
51 Correct 1153 ms 123048 KB Output is correct
52 Correct 193 ms 65616 KB Output is correct
53 Correct 200 ms 66544 KB Output is correct
54 Correct 200 ms 65760 KB Output is correct
55 Correct 1129 ms 138424 KB Output is correct
56 Correct 1048 ms 119656 KB Output is correct
57 Correct 1090 ms 123556 KB Output is correct
58 Correct 197 ms 65388 KB Output is correct
59 Correct 201 ms 66652 KB Output is correct
60 Correct 205 ms 65892 KB Output is correct
61 Correct 1397 ms 124760 KB Output is correct
62 Correct 1387 ms 126884 KB Output is correct
63 Correct 1356 ms 120664 KB Output is correct
64 Correct 1099 ms 126944 KB Output is correct
65 Correct 1127 ms 126236 KB Output is correct
66 Correct 1161 ms 123076 KB Output is correct
67 Correct 227 ms 65520 KB Output is correct
68 Correct 214 ms 66148 KB Output is correct
69 Correct 197 ms 66312 KB Output is correct
70 Correct 1093 ms 117212 KB Output is correct
71 Correct 1148 ms 120804 KB Output is correct
72 Correct 1107 ms 132176 KB Output is correct
73 Correct 193 ms 66192 KB Output is correct
74 Correct 202 ms 65624 KB Output is correct
75 Correct 197 ms 65600 KB Output is correct
76 Correct 7 ms 16340 KB Output is correct
77 Correct 8 ms 16340 KB Output is correct
78 Correct 8 ms 16340 KB Output is correct
79 Correct 1258 ms 115768 KB Output is correct
80 Correct 1358 ms 130592 KB Output is correct
81 Correct 1419 ms 119512 KB Output is correct
82 Correct 1128 ms 120388 KB Output is correct
83 Correct 1187 ms 122216 KB Output is correct
84 Correct 1180 ms 130348 KB Output is correct
85 Correct 205 ms 66756 KB Output is correct
86 Correct 197 ms 66292 KB Output is correct
87 Correct 197 ms 65388 KB Output is correct
88 Correct 1068 ms 135408 KB Output is correct
89 Runtime error 427 ms 1048576 KB Execution killed with signal 9
90 Halted 0 ms 0 KB -