oj.uz

Submission #831917

# Submission time Handle Problem Language Result Execution time Memory
831917 2023-08-20T17:39:01 Z NK_ Grapevine (NOI22_grapevine) C++17
68 / 100
 1956 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
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); sub[u] += sub[v];
		}
	}
	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 <= siz[c]);
	T[c].init(siz[c]);

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

	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) 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;

			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;

				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);
			}
		}

		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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20692 KB Output is correct
2 Correct 18 ms 20692 KB Output is correct
3 Correct 20 ms 20836 KB Output is correct
4 Correct 19 ms 20820 KB Output is correct
5 Correct 18 ms 20792 KB Output is correct
6 Correct 18 ms 20796 KB Output is correct
7 Correct 15 ms 19904 KB Output is correct
8 Correct 12 ms 19924 KB Output is correct
9 Correct 12 ms 19924 KB Output is correct
10 Correct 18 ms 20820 KB Output is correct
11 Correct 19 ms 20800 KB Output is correct
12 Correct 18 ms 20924 KB Output is correct
13 Correct 12 ms 19968 KB Output is correct
14 Correct 13 ms 19912 KB Output is correct
15 Correct 12 ms 19896 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1540 ms 131876 KB Output is correct
2 Correct 1524 ms 132840 KB Output is correct
3 Correct 1563 ms 132024 KB Output is correct
4 Correct 1136 ms 144412 KB Output is correct
5 Correct 1205 ms 134288 KB Output is correct
6 Correct 1136 ms 136912 KB Output is correct
7 Correct 206 ms 63152 KB Output is correct
8 Correct 205 ms 62396 KB Output is correct
9 Correct 205 ms 62360 KB Output is correct
10 Correct 1124 ms 141616 KB Output is correct
11 Correct 1140 ms 138812 KB Output is correct
12 Correct 1198 ms 145608 KB Output is correct
13 Correct 209 ms 62596 KB Output is correct
14 Correct 237 ms 62608 KB Output is correct
15 Correct 221 ms 62992 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 543088 KB Output is correct
2 Correct 1772 ms 545096 KB Output is correct
3 Correct 1752 ms 546348 KB Output is correct
4 Correct 1726 ms 522420 KB Output is correct
5 Correct 1956 ms 524284 KB Output is correct
6 Correct 1778 ms 520944 KB Output is correct
7 Correct 1802 ms 519856 KB Output is correct
8 Correct 1782 ms 541768 KB Output is correct
9 Correct 1717 ms 521168 KB Output is correct
10 Correct 1678 ms 545132 KB Output is correct
11 Correct 1821 ms 522764 KB Output is correct
12 Correct 1648 ms 517740 KB Output is correct
13 Correct 1711 ms 541752 KB Output is correct
14 Correct 1707 ms 517464 KB Output is correct
15 Correct 1656 ms 522704 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1748 ms 141452 KB Output is correct
2 Correct 1733 ms 145920 KB Output is correct
3 Correct 1645 ms 129220 KB Output is correct
4 Correct 1326 ms 143420 KB Output is correct
5 Correct 1336 ms 141288 KB Output is correct
6 Correct 1307 ms 142972 KB Output is correct
7 Correct 224 ms 62924 KB Output is correct
8 Correct 218 ms 63556 KB Output is correct
9 Correct 224 ms 62908 KB Output is correct
10 Correct 1302 ms 155936 KB Output is correct
11 Correct 1215 ms 136596 KB Output is correct
12 Correct 1290 ms 141172 KB Output is correct
13 Correct 247 ms 62688 KB Output is correct
14 Correct 224 ms 63700 KB Output is correct
15 Correct 230 ms 63108 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1757 ms 140104 KB Output is correct
2 Correct 1753 ms 142080 KB Output is correct
3 Correct 1713 ms 135876 KB Output is correct
4 Correct 1268 ms 143280 KB Output is correct
5 Correct 1304 ms 142952 KB Output is correct
6 Correct 1252 ms 141640 KB Output is correct
7 Correct 224 ms 62624 KB Output is correct
8 Correct 222 ms 63024 KB Output is correct
9 Correct 242 ms 63164 KB Output is correct
10 Correct 1241 ms 133232 KB Output is correct
11 Correct 1246 ms 136664 KB Output is correct
12 Correct 1251 ms 150672 KB Output is correct
13 Correct 219 ms 63144 KB Output is correct
14 Correct 212 ms 62544 KB Output is correct
15 Correct 216 ms 62688 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20692 KB Output is correct
2 Correct 18 ms 20692 KB Output is correct
3 Correct 20 ms 20836 KB Output is correct
4 Correct 19 ms 20820 KB Output is correct
5 Correct 18 ms 20792 KB Output is correct
6 Correct 18 ms 20796 KB Output is correct
7 Correct 15 ms 19904 KB Output is correct
8 Correct 12 ms 19924 KB Output is correct
9 Correct 12 ms 19924 KB Output is correct
10 Correct 18 ms 20820 KB Output is correct
11 Correct 19 ms 20800 KB Output is correct
12 Correct 18 ms 20924 KB Output is correct
13 Correct 12 ms 19968 KB Output is correct
14 Correct 13 ms 19912 KB Output is correct
15 Correct 12 ms 19896 KB Output is correct
16 Correct 1540 ms 131876 KB Output is correct
17 Correct 1524 ms 132840 KB Output is correct
18 Correct 1563 ms 132024 KB Output is correct
19 Correct 1136 ms 144412 KB Output is correct
20 Correct 1205 ms 134288 KB Output is correct
21 Correct 1136 ms 136912 KB Output is correct
22 Correct 206 ms 63152 KB Output is correct
23 Correct 205 ms 62396 KB Output is correct
24 Correct 205 ms 62360 KB Output is correct
25 Correct 1124 ms 141616 KB Output is correct
26 Correct 1140 ms 138812 KB Output is correct
27 Correct 1198 ms 145608 KB Output is correct
28 Correct 209 ms 62596 KB Output is correct
29 Correct 237 ms 62608 KB Output is correct
30 Correct 221 ms 62992 KB Output is correct
31 Correct 1736 ms 543088 KB Output is correct
32 Correct 1772 ms 545096 KB Output is correct
33 Correct 1752 ms 546348 KB Output is correct
34 Correct 1726 ms 522420 KB Output is correct
35 Correct 1956 ms 524284 KB Output is correct
36 Correct 1778 ms 520944 KB Output is correct
37 Correct 1802 ms 519856 KB Output is correct
38 Correct 1782 ms 541768 KB Output is correct
39 Correct 1717 ms 521168 KB Output is correct
40 Correct 1678 ms 545132 KB Output is correct
41 Correct 1821 ms 522764 KB Output is correct
42 Correct 1648 ms 517740 KB Output is correct
43 Correct 1711 ms 541752 KB Output is correct
44 Correct 1707 ms 517464 KB Output is correct
45 Correct 1656 ms 522704 KB Output is correct
46 Correct 1748 ms 141452 KB Output is correct
47 Correct 1733 ms 145920 KB Output is correct
48 Correct 1645 ms 129220 KB Output is correct
49 Correct 1326 ms 143420 KB Output is correct
50 Correct 1336 ms 141288 KB Output is correct
51 Correct 1307 ms 142972 KB Output is correct
52 Correct 224 ms 62924 KB Output is correct
53 Correct 218 ms 63556 KB Output is correct
54 Correct 224 ms 62908 KB Output is correct
55 Correct 1302 ms 155936 KB Output is correct
56 Correct 1215 ms 136596 KB Output is correct
57 Correct 1290 ms 141172 KB Output is correct
58 Correct 247 ms 62688 KB Output is correct
59 Correct 224 ms 63700 KB Output is correct
60 Correct 230 ms 63108 KB Output is correct
61 Correct 1757 ms 140104 KB Output is correct
62 Correct 1753 ms 142080 KB Output is correct
63 Correct 1713 ms 135876 KB Output is correct
64 Correct 1268 ms 143280 KB Output is correct
65 Correct 1304 ms 142952 KB Output is correct
66 Correct 1252 ms 141640 KB Output is correct
67 Correct 224 ms 62624 KB Output is correct
68 Correct 222 ms 63024 KB Output is correct
69 Correct 242 ms 63164 KB Output is correct
70 Correct 1241 ms 133232 KB Output is correct
71 Correct 1246 ms 136664 KB Output is correct
72 Correct 1251 ms 150672 KB Output is correct
73 Correct 219 ms 63144 KB Output is correct
74 Correct 212 ms 62544 KB Output is correct
75 Correct 216 ms 62688 KB Output is correct
76 Correct 11 ms 19116 KB Output is correct
77 Correct 10 ms 19028 KB Output is correct
78 Correct 10 ms 19084 KB Output is correct
79 Correct 1677 ms 130788 KB Output is correct
80 Correct 1723 ms 145540 KB Output is correct
81 Correct 1675 ms 134572 KB Output is correct
82 Correct 1363 ms 136920 KB Output is correct
83 Correct 1329 ms 138376 KB Output is correct
84 Correct 1401 ms 148504 KB Output is correct
85 Correct 272 ms 63772 KB Output is correct
86 Correct 278 ms 63516 KB Output is correct
87 Correct 255 ms 62676 KB Output is correct
88 Correct 1474 ms 152708 KB Output is correct
89 Runtime error 672 ms 1048576 KB Execution killed with signal 9
90 Halted 0 ms 0 KB -