Submission #113924

#	Time	Username	Problem	Language	Result	Execution time	Memory
113924		RockyB	Construction of Highway (JOI18_construction)	C++14	16 / 100	2053 ms	15732 KiB

construction

/// In The Name Of God

#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)1e5 + 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];

struct fenwick {
	int f[N];
	inline void upd(int p, int x) {
		for (; p < N; p |= p + 1) f[p] += x;
	}
	inline int get(int p) {
		int res = 0;
		for (; p >= 0; p = (p & (p + 1)) - 1) res += f[p];
		return res;
	}
} T;

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);
	}
}
vector < pair <int, int > > path[N];

inline void paint_v(vector < pair <int, int> > &x, int L, int c) {
	reverse(all(x));
	int add = L;
	while (sz(x)) {
		auto &it = x.back();
		if (it.s <= L) {
			L -= it.s;
			x.pp();
		}
		else {
			it.s -= L;
			break;
		}
	}
	x.pb({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]].back();
			if (it.s <= cut) {
				cut -= it.s;
				path[up[v]].pp();
			}
			else {
				it.s -= cut;
				break;
			}
		}
		path[up[v]].pb({x, L});
		reverse(all(path[up[v]]));
		v = par[up[v]];
	}
}
inline ll inv(vector < pair <int, int > > &x) {
	ll sum = 0;
	for (auto it : x) {
		sum += (ll)T.get(it.f - 1) * it.s;
		T.upd(it.f, it.s);
	}
	for (auto it : x) {
		T.upd(it.f, -it.s);
	}
	return sum;
}
inline void calc(int v, int u) {
	vector < pair <int, int> > s;
	int L = dep[v] - dep[up[v]] + 1, V = v;
	for (auto it : path[up[v]]) {
		if (it.s < L) {
			if (sz(s) && s.back().f == it.f) {
				s[sz(s) - 1].s += it.s;
			}
			else {
				s.pb(it);
			}
			L -= it.s;
		}
		else {
			if (sz(s) && s.back().f == it.f) {
				s[sz(s) - 1].s += L;
			}
			else {
				s.pb({it.f, L});
			}
			break;
		}
	}
	reverse(all(s));
	v = par[up[v]];
	while (v) {
		int need = dep[v] - dep[up[v]] + 1;
		vector < pair <int, int > > add;
		for (auto it : path[up[v]]) {
			if (it.s < need) {
				add.pb(it);
				need -= it.s;
			}
			else {
				add.pb({it.f, need});
				break;
			}
		}
		reverse(all(add));
		for (auto it : add) {
			if (sz(s) && s.back().f == it.f) {
				s[sz(s) - 1].s += it.s;
			}
			else {
				s.pb(it);
			}
		}
		v = par[up[v]];
	}

	ll cnt = inv(s);
	/*
	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();
	
	{ /// compressing
		vector <int> cmp;
		rep(i, 1, n) {
			cmp.pb(a[i]);
		}
		sort(all(cmp));
		cmp.erase(unique(all(cmp)), cmp.end());
		rep(i, 1, n) {
			a[i] = lower_bound(all(cmp), a[i]) - cmp.begin();
		}
	}
	rep(i, 2, n) {
		calc(e[i].f, e[i].s);
	}
	ioi
}

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