Submission #873847

#	Time	Username	Problem	Language	Result	Execution time	Memory
873847		NK_	Construction of Highway (JOI18_construction)	C++17	100 / 100	310 ms	21120 KiB

construction

// 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 f first
#define s second
#define mp make_pair

#define sz(x) int(x.size())

using pi = pair<int, int>;
using ll = long long;

template<class T> using V = vector<T>;

using vi = V<int>;
using vpi = V<pi>;

const int LG = 18;

struct BIT {
	vi data; int N; void init(int n) { N = n; data = vi(N, 0); }
	void add(int p, int x) { for(++p; p <= N; p += p & -p) data[p - 1] += x; }
	int sum(int l, int r) { return sum(r + 1) - sum(l); }
	int sum(int r) { int s = 0; for(; r; r -= r & -r) s += data[r - 1]; return s; }
};

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

	int N; cin >> N;
	vi A(N); for(auto& x : A) cin >> x;

	{
		vi C = A; sort(begin(C), end(C));
		for(auto& x : A) x = lower_bound(begin(C), end(C), x) - begin(C);
	}

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



	vi nxt(N), par(N), dep(N, 0), siz(N); V<vpi> st(N); 

	function<void(int)> gen = [&](int u) {
		for(auto& v : adj[u]) {
			dep[v] = dep[u] + 1;
			par[v] = u;
			gen(v);
			siz[u] += siz[v];
		}
	};


	function<void(int, int)> dfs = [&](int u, int h) {
		nxt[u] = h;

		int hvy = -1;
		for(auto& v : adj[u]) {
			if (hvy == -1 || siz[hvy] < siz[v]) hvy = v;
		}

		if (hvy == -1) return;

		dfs(hvy, h);
		for(auto& v : adj[u]) if (v != hvy) dfs(v, v);
	};

	gen(0);
	par[0] = -1; dfs(0, 0);

	BIT B; B.init(N);

	auto answer = [&](vpi &X) {
		ll ans = 0;

		for(auto& x : X) {
			// cout << x.f << " => " << x.s << endl;
			ans += x.s * 1LL * B.sum(x.f);
			B.add(x.f, x.s);
		}

		for(auto& x : X) B.add(x.f, -x.s);

		cout << ans << endl;
	};

	for(auto u : Q) {
		vpi X; int c = A[u];
 	
		while(u != -1) {
			// cout << "U: " << u << endl;
			int d = dep[u]; vpi R;

			u = nxt[u]; int t = dep[u] - 1; // cout << "C: " << u << endl;
			while(sz(st[u]) && st[u].back().s <= d) {
				pi bk = st[u].back(); // cout << bk.f << " -> " << bk.s << endl;
				R.pb(mp(bk.f, bk.s - t)); t = bk.s;
				st[u].pop_back();
			}

			if (sz(st[u])) R.pb(mp(st[u].back().f, d - t));

			st[u].pb(mp(c, d));

			reverse(begin(R), end(R));
			X.insert(end(X), begin(R), end(R));

			u = par[u];
		}


		answer(X);
		// cout << endl << endl << endl;
	}




	exit(0-0);
}	

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84