Submission #529126

#	Time	Username	Problem	Language	Result	Execution time	Memory
529126		fhvirus	Construction of Highway (JOI18_construction)	C++17	100 / 100	214 ms	20804 KiB

construction

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif

struct LISAN : vector<int> {
	void done() { sort(AI()); erase(unique(AI()), end()); }
	int operator () (const int& v) const { return lower_bound(AI(), v) - begin(); }
};
struct BIT {
	int n; vector<int> val;
	BIT(int _n = 0): n(_n), val(n + 1, 0) {}
	void modify(int p, int v) {
		for (; p <= n; p += p & -p)
			val[p] += v;
	}
	int query(int p) {
		int r = 0;
		for (; p > 0; p -= p & -p)
			r += val[p];
		return r;
	}
};

const int kN = 100'001;
int N, C[kN], A[kN], B[kN];
int par[kN];
vector<int> chi[kN];

int dep[kN], siz[kN];
void dfs_siz(int u) {
	siz[u] = 1;
	for (int& v: chi[u]) {
		dep[v] = dep[u] + 1;
		dfs_siz(v);
		siz[u] += siz[v];
		if (siz[v] > siz[chi[u][0]])
			swap(v, chi[u][0]);
	}
}
vector<pii> chain[kN];
int head[kN];
void dfs_head(int u, int h) {
	head[u] = h;
	for (const int& v: chi[u])
		dfs_head(v, v == chi[u][0] ? h : v);
	if (chain[h].empty())
		chain[h].pb(-1, dep[u] + 1);
	if (chain[h].back().ff != C[u])
		chain[h].pb(C[u], dep[u]);
	else
		chain[h].back().ss = dep[u];
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	LISAN lisan;
	for (int i = 1; i <= N; ++i) {
		cin >> C[i];
		lisan.pb(C[i]);
	}
	lisan.done();
	for (int i = 1; i <= N; ++i)
		C[i] = lisan(C[i]) + 1;
	for (int i = 1; i < N; ++i) {
		cin >> A[i] >> B[i];
		par[B[i]] = A[i];
		chi[A[i]].pb(B[i]);
	}

	dfs_siz(1);
	dfs_head(1, 1);

	BIT bit(lisan.size());
	vector<pii> vals, tmp;
	for (int i = 1; i < N; ++i) {
		int u = A[i];
		do {
			int h = head[u];
			while (8e7 /* is stronger than me */ ) {
				pii cur = chain[h].back();
				if (cur.ss > dep[u]) break;
				chain[h].pop_back();
				if (chain[h].back().ss > dep[u]) {
					tmp.pb(cur.ff, dep[u] - cur.ss + 1);
					if (chain[h].back().ss > dep[u] + 1)
						chain[h].pb(cur.ff, dep[u] + 1);
					break;
				}
				tmp.pb(cur.ff, chain[h].back().ss - cur.ss);
			}
			while (!tmp.empty()) {
				vals.push_back(tmp.back());
				tmp.pop_back();
			}
			u = par[h];
		} while (u != 0);

		ll ans = 0;
		for (const auto& [val, num]: vals) {
			ans += 1ll * bit.query(val - 1) * num;
			bit.modify(val, num);
		}
		cout << ans << '\n';
		for (const auto& [val, num]: vals)
			bit.modify(val, -num);
		vals.clear();

		u = A[i];
		do {
			int h = head[u];
			chain[h].pb(C[B[i]], dep[h]);
			u = par[h];
		} while (u != 0);
	}
	
	return 0;
}

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