oj.uz

Submission #831959

# Submission time Handle Problem Language Result Execution time Memory
831959 2023-08-20T18:35:46 Z NK_ Grapevine (NOI22_grapevine) C++17
6 / 100
 229 ms 167124 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);
const int nax = 1e5 + 5;
const int LG = 17;
const int MEM = 1e7;

int amt = 5 * nax * LG;

// 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;
		amt += 4 * n;
		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
 
 
 
// MAIN
vpi adj[nax]; int W[nax];
 
// CENTROID
int sub[nax], proc[nax], siz[nax];
 
// CENTROID SUBTREES
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]);
	assert(amt <= MEM);
 
	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:164:6: warning: unused variable 'R' [-Wunused-variable]
  164 |  int R = init();
      |      ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17880 KB Output is correct
2 Correct 13 ms 17876 KB Output is correct
3 Correct 18 ms 17872 KB Output is correct
4 Correct 18 ms 17924 KB Output is correct
5 Correct 14 ms 17876 KB Output is correct
6 Correct 13 ms 17876 KB Output is correct
7 Correct 8 ms 17236 KB Output is correct
8 Correct 9 ms 17236 KB Output is correct
9 Correct 9 ms 17336 KB Output is correct
10 Correct 15 ms 17876 KB Output is correct
11 Correct 14 ms 17896 KB Output is correct
12 Correct 16 ms 17984 KB Output is correct
13 Correct 9 ms 17232 KB Output is correct
14 Correct 12 ms 17312 KB Output is correct
15 Correct 10 ms 17236 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 214 ms 126552 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 167124 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 178 ms 126264 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 128316 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17880 KB Output is correct
2 Correct 13 ms 17876 KB Output is correct
3 Correct 18 ms 17872 KB Output is correct
4 Correct 18 ms 17924 KB Output is correct
5 Correct 14 ms 17876 KB Output is correct
6 Correct 13 ms 17876 KB Output is correct
7 Correct 8 ms 17236 KB Output is correct
8 Correct 9 ms 17236 KB Output is correct
9 Correct 9 ms 17336 KB Output is correct
10 Correct 15 ms 17876 KB Output is correct
11 Correct 14 ms 17896 KB Output is correct
12 Correct 16 ms 17984 KB Output is correct
13 Correct 9 ms 17232 KB Output is correct
14 Correct 12 ms 17312 KB Output is correct
15 Correct 10 ms 17236 KB Output is correct
16 Runtime error 214 ms 126552 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -