Submission #44387

#	Time	Username	Problem	Language	Result	Execution time	Memory
44387		Bruteforceman	Construction of Highway (JOI18_construction)	C++11	16 / 100	1091 ms	30364 KiB

construction

#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
int l[100010], r[100010];
int c[100010];
int n;
vector <int> g[100010];
int sub[100010];
int big[100010];
int head[100010];
int pos[100010];

void dfs(int x) {
	big[x] = -1;
	sub[x] = 1;
	for(auto i : g[x]) {
		dfs(i);
		sub[x] += sub[i];
		if(big[x] == -1 || sub[big[x]] < sub[i]) {
			big[x] = i;
		}
	}
}
int mx[100010 * 4];
int mn[100010 * 4];
int prop[100010 * 4];
int par[100010];
int dp[20][100010];
const int logn = 19;

void pushdown(int c) {
	if(prop[c] == -1) return ;
	int l = c << 1;
	int r = l + 1;
	prop[l] = prop[r] = prop[c];
	mx[l] = mx[r] = prop[c];
	mn[l] = mn[r] = prop[c];
	prop[c] = -1;
}

void update(int x, int y, int val, int c = 1, int b = 1, int e = n) {
	if(x <= b && e <= y) {
		mn[c] = mx[c] = val;
		prop[c] = val;
		return ;
	}
	if(y < b || e < x) return ;
	pushdown(c);

	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	update(x, y, val, l, b, m);
	update(x, y, val, r, m+1, e);
	mn[c] = min(mn[l], mn[r]);
	mx[c] = max(mx[l], mx[r]);
}

int query(int x, int val, int c = 1, int b = 1, int e = n) {
	if(mx[c] == mn[c]) {
		return mx[c] == val ? x - b + 1 : 0;
	}
	if(b == e) return mx[c] == val;
	pushdown(c);
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) return query(x, val, l, b, m);
	else {
		int len = query(x, val, r, m + 1, e);
		if(x - m == len) {
			return query(m, val, l, b, m) + len;
		} else {
			return len;
		}
	}
} 
int get(int x, int c = 1, int b = 1, int e = n) {
	if(b == e) return mx[c];
	pushdown(c);
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) return get(x, l, b, m);
	else return get(x, r, m+1, e); 
}

void precalc() {
	memset(prop, -1, sizeof prop);
	int cur = 0;
	for(int i = 1; i <= n; i++) {
		if(par[i] == -1 || big[par[i]] != i) {
			for(int j = i; j != -1; j = big[j]) {
				pos[j] = ++cur;
				head[j] = i;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		update(pos[i], pos[i], c[i]);
	}
	dp[0][1] = 0;
	for(int i = 2; i <= n; i++) dp[0][i] = par[i];
	for(int i = 1; i <= logn; i++) {
		for(int j = 1; j <= n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
}
void change(int x) {
	int cur = x;
	while(cur != -1) {
		update(pos[head[cur]], pos[cur], c[x]);
		cur = head[cur];
		cur = par[cur];
	}
}
int lift(int node, int up) {
	for(int i = logn; i >= 0; i--) {
		if((1 << i) <= up) {
			node = dp[i][node];
			up -= 1 << i;
		}
	}
	return node;
}
 
int bit[100010];
void upd(int x, int val) {
	x += 1;
	for(int i = x; i <= n; i += i & (-i)) {
		bit[i] += val;
	} 
}
int total(int x) {
	x += 1;
	int ans = 0;
	for(int i = x; i > 0; i -= i & (-i)) {
		ans += bit[i];
	}
	return ans;
}
long long inverse(vector <pii> v) {
	long long ans = 0;
	vector <int> idx;
	for(int i = 0; i < v.size(); i++) {
		idx.push_back(i);
	}
	auto cmp = [&v] (int a, int b) { 
		if(v[a].first == v[b].first) return a > b;
		else return v[a].first < v[b].first;
	};
	sort(idx.begin(), idx.end(), cmp);
	for(int i : idx) {
		ans += 1LL * v[i].second * total(i);
		upd(i, v[i].second);
	}
	for(auto i : idx) {
		upd(i, -v[i].second);
	}
	return ans;
}

long long getCost(int x) {
	vector <pii> v;
	int cur = par[x];
	while(cur > 0) {
		int val = get(pos[cur]);
		int len = min(query(pos[cur], val), pos[cur] - pos[head[cur]] + 1);
		v.push_back(pii(val, len));
		cur = lift(cur, len);
	} 
	return inverse(v);
} 
int main(int argc, char const *argv[])
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}
	par[1] = -1;
	for(int i = 1; i < n; i++) {
		scanf("%d %d", &l[i], &r[i]);
		g[l[i]].push_back(r[i]);
		par[r[i]] = l[i];
	}
	dfs(1);
	precalc();
	for(int i = 1; i < n; i++) {
		printf("%lld\n", getCost(r[i]));
		change(r[i]);
	}
	return 0;	
}

Compilation message (stderr)

construction.cpp: In function 'long long int inverse(std::vector<std::pair<int, int> >)':
construction.cpp:146:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
construction.cpp: In function 'int main(int, const char**)':
construction.cpp:177:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
construction.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~
construction.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &l[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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