Submission #44594

#	Time	Username	Problem	Language	Result	Execution time	Memory
44594		aome	Construction of Highway (JOI18_construction)	C++17	100 / 100	628 ms	176668 KiB

construction

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct Data {
	int l, r, c;
};

int n, c[N];
int a[N], b[N];
int par[N], nchild[N];
int T, head[N], pos[N];
int bit[N];
vector<int> G[N];
deque<Data> dq[N];

void dfs(int u) {
	nchild[u] = 1;
	for (auto v : G[u]) {
		dfs(v), nchild[u] += nchild[v];
	}
}

void dfsHld(int u) {
	if (!head[u]) head[u] = u;
	pos[u] = ++T;
	int cur = 0;
	for (auto v : G[u]) {
		if (cur == 0 || nchild[cur] < nchild[v]) cur = v;
	}
	if (cur) head[cur] = head[u], dfsHld(cur);
	for (auto v : G[u]) {
		if (v != cur) dfsHld(v);
	}
}

void upd(int x, int y) {
	for (; x <= n; x += x & -x) bit[x] += y;
}

int get(int x) {
	int ret = 0; for (; x > 0; x -= x & -x) ret += bit[x]; return ret;
}

void updHld(int u, int c) {
	while (u) {
		int pu = pos[u];
		u = head[u];
		while (dq[u].size()) {
			Data tmp = dq[u].front();
			if (tmp.r <= pu) dq[u].pop_front();
			else {
				dq[u][0].l = pu + 1; break;
			}
		}
		dq[u].push_front({pos[u], pu, c});
		u = par[u];
	}	
}

void getHld(int u) {
	long long res = 0;
	vector< pair<int, int> > buffer;
	while (u) {
		int pu = pos[u];
		u = head[u];
		if (dq[u].size()) {
			int ptr = 0;
			for (ptr; ptr < dq[u].size(); ++ptr) {
				if (pu <= dq[u][ptr].r) break;
			}
			if (ptr == dq[u].size()) ptr--;
			for (ptr; ptr >= 0; --ptr) {
				int cnt = min(dq[u][ptr].r, pu) - dq[u][ptr].l + 1;
				res += 1LL * get(dq[u][ptr].c - 1) * cnt;
				upd(dq[u][ptr].c, cnt);
				buffer.push_back({dq[u][ptr].c, -cnt});
			}
		}
		u = par[u];
	}
	for (auto i : buffer) upd(i.first, i.second);
	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	vector<int> vec;
	for (int i = 1; i <= n; ++i) cin >> c[i], vec.push_back(c[i]);
	sort(vec.begin(), vec.end());
	for (int i = 1; i <= n; ++i) c[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1;
	for (int i = 1; i < n; ++i) {
		cin >> a[i] >> b[i], G[a[i]].push_back(b[i]), par[b[i]] = a[i];
	}
	dfs(1), dfsHld(1);
	dq[head[1]].push_back({pos[1], pos[1], c[1]});
	for (int i = 1; i < n; ++i) {
		getHld(b[i]);
		updHld(b[i], c[b[i]]);
		// for (int j = 1; j <= n; ++j) {
		// 	if (j == head[j]) {
		// 		cout << "#check dq " << j << '\n';
		// 		for (auto k : dq[j]) {
		// 			cout << k.l << ' ' << k.r << ' ' << k.c << '\n';
		// 		}
		// 	}
		// }
	}
}

Compilation message (stderr)

construction.cpp: In function 'void getHld(int)':
construction.cpp:71:12: warning: statement has no effect [-Wunused-value]
    for (ptr; ptr < dq[u].size(); ++ptr) {
            ^
construction.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (ptr; ptr < dq[u].size(); ++ptr) {
              ~~~~^~~~~~~~~~~~~~
construction.cpp:74:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ptr == dq[u].size()) ptr--;
        ~~~~^~~~~~~~~~~~~~~
construction.cpp:75:12: warning: statement has no effect [-Wunused-value]
    for (ptr; ptr >= 0; --ptr) {
            ^

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