Submission #113958

#	Time	Username	Problem	Language	Result	Execution time	Memory
113958		RockyB	Construction of Highway (JOI18_construction)	C++17	100 / 100	427 ms	153872 KiB

construction

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n;
int a[N];

pair <int, int> e[N];
vector <int> g[N];

int sz[N], up[N], par[N], len[N], dep[N];

inline void dfs_sz(int v = 1, int p = 0) {
	sz[v]++;
	par[v] = p;
	dep[v] = dep[p] + 1;
	for (auto &to : g[v]) {
		if (to != p) {
			dfs_sz(to, v);
			sz[v] += sz[to];
			if (sz[to] > sz[g[v][0]]) swap(g[v][0], to);
		}
	}
}
inline void dfs(int v = 1) {
	len[up[v]]++;
	for (auto to : g[v]) {
		up[to] = (to == g[v][0] ? up[v] : to);
		dfs(to);
	}
}
deque < pair <int, int > > path[N];

inline void paint_v(deque < pair <int, int> > &x, int L, int c) {
	//reverse(all(x));
	int add = L;
	while (sz(x)) {
		auto &it = x.front();
		if (it.s <= L) {
			L -= it.s;
			x.pop_front();
		}
		else {
			it.s -= L;
			break;
		}
	}
	x.push_front({c, add});
	//reverse(all(x));
}
inline void paint(int v, int x) {
	paint_v(path[up[v]], dep[v] - dep[up[v]] + 1, x);
	v = par[up[v]];
	while (v) {
		int cut = dep[v] - dep[up[v]] + 1, L = cut;
		//reverse(all(path[up[v]]));
		while (sz(path[up[v]])) {
			auto &it = path[up[v]].front();
			if (it.s <= cut) {
				cut -= it.s;
				path[up[v]].pop_front();
			}
			else {
				it.s -= cut;
				break;
			}
		}
		path[up[v]].push_front({x, L});
		//reverse(all(path[up[v]]));
		v = par[up[v]];
	}
}

int Sz;

pair <int, int> bfr[N], nbfr[N], s[N], add[N];

inline ll inv(int l, int r) {
	if (l >= r) {
		if (l == r) bfr[r] = s[r];
		return 0;
	}
	int mid = (l + r) >> 1;
	ll res = inv(l, mid) + inv(mid + 1, r), pref = 0;
	int ptr = l, pos = l;
	rep(i, mid + 1, r) {
		while (ptr <= mid && bfr[ptr].f < bfr[i].f) {
			pref += bfr[ptr].s;
			nbfr[pos++] = bfr[ptr++];
		}
		nbfr[pos++] = bfr[i];
		res += (ll)bfr[i].s * pref;
	}
	while (ptr <= mid) nbfr[pos++] = bfr[ptr++];
	rep(i, l, r) {
		bfr[i] = nbfr[i];
	}
	return res;
}
inline void calc(int v, int u) {
	Sz = 0;
	int L = dep[v] - dep[up[v]] + 1, V = v;
	for (auto it : path[up[v]]) {
		if (it.s < L) {
			if (Sz && s[Sz - 1].f == it.f) {
				s[Sz - 1].s += it.s;
			}
			else {
				s[Sz++] = it;
			}
			L -= it.s;
		}
		else {
			if (Sz && s[Sz - 1].f == it.f) {
				s[Sz - 1].s += L;
			}
			else {
				s[Sz++] = {it.f, L};
			}
			break;
		}
	}
	reverse (s, s + Sz);
	v = par[up[v]];
	while (v) {
		int need = dep[v] - dep[up[v]] + 1, tmp = 0;

		for (auto it : path[up[v]]) {
			if (it.s < need) {
				add[tmp++] = it;
				need -= it.s;
			}
			else {
				add[tmp++] = {it.f, need};
				break;
			}
		}
		reverse (add, add + tmp);
		rep(i, 0, tmp - 1) {
			auto it = add[i];
			if (Sz && s[Sz - 1].f == it.f) {
				s[Sz - 1].s += it.s;
			}
			else {
				s[Sz++] = it;
			}
		}
		v = par[up[v]];
	}
	ll cnt = inv(0, Sz - 1);
	/*
	rep(i, 0, sz(s) - 1) {
		rep(j, i + 1, sz(s) - 1) {
			if (s[i].f > s[j].f) cnt += s[i].s * 1ll * s[j].s;
		}
	}*/
	paint(V, a[u]);
	if (sz(path[up[u]]) && path[up[u]].back().f == a[u]) {
		path[up[u]][sz(path[up[u]]) - 1].s++;
	}
	else {
		path[up[u]].pb({a[u], 1});
	}
	cout << cnt << nl;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		freopen ("A.out", "w", stdout);
	#endif
	Kazakhstan
	cin >> n;
	rep(i, 1, n) cin >> a[i];
	rep(i, 2, n) {
		cin >> e[i].f >> e[i].s;
		g[e[i].f].pb(e[i].s);
	}
	dfs_sz();
	up[1] = 1;
	dfs();
	
	rep(i, 2, n) {
		calc(e[i].f, e[i].s);
	}
	ioi
}

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