oj.uz

Submission #831931

# Submission time Handle Problem Language Result Execution time Memory
831931 2023-08-20T17:56:02 Z NK_ Grapevine (NOI22_grapevine) C++17
68 / 100
 1583 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 = 19;
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 16 ms 18772 KB Output is correct
2 Correct 14 ms 18772 KB Output is correct
3 Correct 14 ms 18828 KB Output is correct
4 Correct 15 ms 18772 KB Output is correct
5 Correct 14 ms 18700 KB Output is correct
6 Correct 14 ms 18772 KB Output is correct
7 Correct 10 ms 18180 KB Output is correct
8 Correct 10 ms 18112 KB Output is correct
9 Correct 13 ms 18292 KB Output is correct
10 Correct 15 ms 18792 KB Output is correct
11 Correct 21 ms 18704 KB Output is correct
12 Correct 15 ms 18824 KB Output is correct
13 Correct 10 ms 18176 KB Output is correct
14 Correct 11 ms 18116 KB Output is correct
15 Correct 10 ms 18188 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 121380 KB Output is correct
2 Correct 1253 ms 122760 KB Output is correct
3 Correct 1213 ms 121816 KB Output is correct
4 Correct 1012 ms 130236 KB Output is correct
5 Correct 951 ms 122868 KB Output is correct
6 Correct 986 ms 125188 KB Output is correct
7 Correct 201 ms 70792 KB Output is correct
8 Correct 182 ms 69792 KB Output is correct
9 Correct 187 ms 69904 KB Output is correct
10 Correct 1002 ms 127164 KB Output is correct
11 Correct 957 ms 125732 KB Output is correct
12 Correct 991 ms 128684 KB Output is correct
13 Correct 172 ms 69944 KB Output is correct
14 Correct 181 ms 70012 KB Output is correct
15 Correct 191 ms 70600 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1478 ms 532260 KB Output is correct
2 Correct 1555 ms 534312 KB Output is correct
3 Correct 1500 ms 535520 KB Output is correct
4 Correct 1463 ms 511756 KB Output is correct
5 Correct 1506 ms 513552 KB Output is correct
6 Correct 1505 ms 510340 KB Output is correct
7 Correct 1535 ms 509384 KB Output is correct
8 Correct 1508 ms 531056 KB Output is correct
9 Correct 1468 ms 510568 KB Output is correct
10 Correct 1483 ms 534168 KB Output is correct
11 Correct 1483 ms 512020 KB Output is correct
12 Correct 1426 ms 507280 KB Output is correct
13 Correct 1504 ms 531000 KB Output is correct
14 Correct 1433 ms 506904 KB Output is correct
15 Correct 1476 ms 512056 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1367 ms 131124 KB Output is correct
2 Correct 1365 ms 135584 KB Output is correct
3 Correct 1248 ms 119124 KB Output is correct
4 Correct 1184 ms 130112 KB Output is correct
5 Correct 1161 ms 126332 KB Output is correct
6 Correct 1189 ms 127664 KB Output is correct
7 Correct 213 ms 70364 KB Output is correct
8 Correct 202 ms 71396 KB Output is correct
9 Correct 220 ms 70564 KB Output is correct
10 Correct 1209 ms 143120 KB Output is correct
11 Correct 1090 ms 124468 KB Output is correct
12 Correct 1162 ms 128240 KB Output is correct
13 Correct 224 ms 70080 KB Output is correct
14 Correct 204 ms 71596 KB Output is correct
15 Correct 221 ms 70696 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 129700 KB Output is correct
2 Correct 1539 ms 131700 KB Output is correct
3 Correct 1578 ms 125600 KB Output is correct
4 Correct 1206 ms 131800 KB Output is correct
5 Correct 1103 ms 131148 KB Output is correct
6 Correct 1131 ms 127972 KB Output is correct
7 Correct 235 ms 70104 KB Output is correct
8 Correct 193 ms 70620 KB Output is correct
9 Correct 243 ms 70808 KB Output is correct
10 Correct 1109 ms 121992 KB Output is correct
11 Correct 1069 ms 125700 KB Output is correct
12 Correct 1171 ms 137056 KB Output is correct
13 Correct 233 ms 70788 KB Output is correct
14 Correct 221 ms 70096 KB Output is correct
15 Correct 226 ms 70172 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18772 KB Output is correct
2 Correct 14 ms 18772 KB Output is correct
3 Correct 14 ms 18828 KB Output is correct
4 Correct 15 ms 18772 KB Output is correct
5 Correct 14 ms 18700 KB Output is correct
6 Correct 14 ms 18772 KB Output is correct
7 Correct 10 ms 18180 KB Output is correct
8 Correct 10 ms 18112 KB Output is correct
9 Correct 13 ms 18292 KB Output is correct
10 Correct 15 ms 18792 KB Output is correct
11 Correct 21 ms 18704 KB Output is correct
12 Correct 15 ms 18824 KB Output is correct
13 Correct 10 ms 18176 KB Output is correct
14 Correct 11 ms 18116 KB Output is correct
15 Correct 10 ms 18188 KB Output is correct
16 Correct 1169 ms 121380 KB Output is correct
17 Correct 1253 ms 122760 KB Output is correct
18 Correct 1213 ms 121816 KB Output is correct
19 Correct 1012 ms 130236 KB Output is correct
20 Correct 951 ms 122868 KB Output is correct
21 Correct 986 ms 125188 KB Output is correct
22 Correct 201 ms 70792 KB Output is correct
23 Correct 182 ms 69792 KB Output is correct
24 Correct 187 ms 69904 KB Output is correct
25 Correct 1002 ms 127164 KB Output is correct
26 Correct 957 ms 125732 KB Output is correct
27 Correct 991 ms 128684 KB Output is correct
28 Correct 172 ms 69944 KB Output is correct
29 Correct 181 ms 70012 KB Output is correct
30 Correct 191 ms 70600 KB Output is correct
31 Correct 1478 ms 532260 KB Output is correct
32 Correct 1555 ms 534312 KB Output is correct
33 Correct 1500 ms 535520 KB Output is correct
34 Correct 1463 ms 511756 KB Output is correct
35 Correct 1506 ms 513552 KB Output is correct
36 Correct 1505 ms 510340 KB Output is correct
37 Correct 1535 ms 509384 KB Output is correct
38 Correct 1508 ms 531056 KB Output is correct
39 Correct 1468 ms 510568 KB Output is correct
40 Correct 1483 ms 534168 KB Output is correct
41 Correct 1483 ms 512020 KB Output is correct
42 Correct 1426 ms 507280 KB Output is correct
43 Correct 1504 ms 531000 KB Output is correct
44 Correct 1433 ms 506904 KB Output is correct
45 Correct 1476 ms 512056 KB Output is correct
46 Correct 1367 ms 131124 KB Output is correct
47 Correct 1365 ms 135584 KB Output is correct
48 Correct 1248 ms 119124 KB Output is correct
49 Correct 1184 ms 130112 KB Output is correct
50 Correct 1161 ms 126332 KB Output is correct
51 Correct 1189 ms 127664 KB Output is correct
52 Correct 213 ms 70364 KB Output is correct
53 Correct 202 ms 71396 KB Output is correct
54 Correct 220 ms 70564 KB Output is correct
55 Correct 1209 ms 143120 KB Output is correct
56 Correct 1090 ms 124468 KB Output is correct
57 Correct 1162 ms 128240 KB Output is correct
58 Correct 224 ms 70080 KB Output is correct
59 Correct 204 ms 71596 KB Output is correct
60 Correct 221 ms 70696 KB Output is correct
61 Correct 1417 ms 129700 KB Output is correct
62 Correct 1539 ms 131700 KB Output is correct
63 Correct 1578 ms 125600 KB Output is correct
64 Correct 1206 ms 131800 KB Output is correct
65 Correct 1103 ms 131148 KB Output is correct
66 Correct 1131 ms 127972 KB Output is correct
67 Correct 235 ms 70104 KB Output is correct
68 Correct 193 ms 70620 KB Output is correct
69 Correct 243 ms 70808 KB Output is correct
70 Correct 1109 ms 121992 KB Output is correct
71 Correct 1069 ms 125700 KB Output is correct
72 Correct 1171 ms 137056 KB Output is correct
73 Correct 233 ms 70788 KB Output is correct
74 Correct 221 ms 70096 KB Output is correct
75 Correct 226 ms 70172 KB Output is correct
76 Correct 8 ms 17156 KB Output is correct
77 Correct 9 ms 17108 KB Output is correct
78 Correct 8 ms 17108 KB Output is correct
79 Correct 1569 ms 120600 KB Output is correct
80 Correct 1583 ms 135212 KB Output is correct
81 Correct 1347 ms 124112 KB Output is correct
82 Correct 1327 ms 125208 KB Output is correct
83 Correct 1136 ms 126944 KB Output is correct
84 Correct 1171 ms 135008 KB Output is correct
85 Correct 250 ms 71584 KB Output is correct
86 Correct 204 ms 71104 KB Output is correct
87 Correct 198 ms 70152 KB Output is correct
88 Correct 1048 ms 140084 KB Output is correct
89 Runtime error 519 ms 1048576 KB Execution killed with signal 9
90 Halted 0 ms 0 KB -