oj.uz

Submission #828604

# Submission time Handle Problem Language Result Execution time Memory
828604 2023-08-17T12:36:44 Z NK_ Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 49 ms 14644 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 mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;

const int LG = 16;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N; cin >> N;

	V<vpi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}

	vi st(N), en(N), dep(N);
	V<vi> up(N, vi(LG));

	int t = 0;
	function<void(int, int)> gen = [&](int u, int p) {
		up[u][0] = p;
		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		st[u] = t++;
		for(auto& e : adj[u]) if (e.f != p) {
			dep[e.f] = dep[u] + e.s; gen(e.f, u);
		}
		en[u] = t - 1;
	};
	
	dep[0] = 0; gen(0, 0);

	auto anc = [&](int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; };

	auto lca = [&](int a, int b) {
		if (anc(a, b)) return a;

		for(int i = LG - 1; i >= 0; i--) {
			if (anc(up[a][i], b)) a = up[a][i];
		}

		return up[a][0];
	};

	auto dist = [&](int u, int v) {
		// cout << u << " - " << v << " - " << lca(u, v) << endl;
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	};


	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) { 
		vi A(5); for(auto& x : A) cin >> x;

		sort(begin(A), end(A), [&](int x, int y) { return st[x] < st[y]; });

		for(int x = 0; x < 4; x++) A.pb(lca(A[x], A[x+1]));

		sort(begin(A), end(A), [&](int x, int y) { return st[x] < st[y]; });
		A.erase(unique(begin(A), end(A)), end(A));

		vi stk = {-1}; int ans = 0;
		for(auto& x : A) {
			while(stk.back() != -1 && en[stk.back()] < st[x]) stk.pop_back();

			// for(auto& y : stk) cout << y << ", ";
			// cout << endl;

			if (stk.back() != -1) ans += dist(stk.back(), x);
			stk.pb(x);
		}
		// cout << endl;

		cout << ans << nl;
	}

	exit(0-0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12248 KB Output is correct
2 Correct 41 ms 14532 KB Output is correct
3 Correct 39 ms 14444 KB Output is correct
4 Correct 43 ms 14432 KB Output is correct
5 Correct 39 ms 14512 KB Output is correct
6 Correct 39 ms 14540 KB Output is correct
7 Correct 37 ms 14524 KB Output is correct
8 Correct 42 ms 14492 KB Output is correct
9 Correct 49 ms 14644 KB Output is correct
10 Correct 37 ms 14496 KB Output is correct

Subtask #3
0 / 40.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 35 ms 12248 KB Output is correct
3 Correct 41 ms 14532 KB Output is correct
4 Correct 39 ms 14444 KB Output is correct
5 Correct 43 ms 14432 KB Output is correct
6 Correct 39 ms 14512 KB Output is correct
7 Correct 39 ms 14540 KB Output is correct
8 Correct 37 ms 14524 KB Output is correct
9 Correct 42 ms 14492 KB Output is correct
10 Correct 49 ms 14644 KB Output is correct
11 Correct 37 ms 14496 KB Output is correct
12 Incorrect 24 ms 9788 KB Output isn't correct
13 Halted 0 ms 0 KB -