Submission #218235

#	Time	Username	Problem	Language	Result	Execution time	Memory
218235		sunho0371	Putovanje (COCI20_putovanje)	C++14	20 / 110	236 ms	20712 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree {
	vector<int> tree, lazy;
	int height, sz;
	void init(int n) {
		height = (int)ceil(log2(n));
		sz = (1 << height);
		tree.resize((1 << (height + 1)) + 1, 0);
		lazy.resize((1 << (height + 1)) + 1, 0);
	}
	void updatelazy(int left, int right, int treepos) {
		if (left != right) {
			lazy[treepos * 2] += lazy[treepos] / 2;
			lazy[treepos * 2 + 1] += lazy[treepos] / 2;
		}
		tree[treepos] += lazy[treepos];
		lazy[treepos] = 0;
	}
	void updateAll(int left, int right, int treepos) {
		if (lazy[treepos]) updatelazy(left, right, treepos);
		if (left != right) {
			int mid = (left + right) / 2;
			updateAll(left, mid, treepos * 2);
			updateAll(mid + 1, right, treepos * 2 + 1);
		}
	}
	void update(int left, int right, int treepos, int from, int to) {
		if (lazy[treepos]) updatelazy(left, right, treepos);
		if (right < from || to < left) return;
		else if (from <= left && right <= to) {
			tree[treepos] += right - left + 1;
            if (left == right) return;
			lazy[treepos * 2] += (right - left + 1) / 2;
			lazy[treepos * 2 + 1] += (right - left + 1) / 2;
		}
		else {
			int mid = (left + right) / 2;
			update(left, mid, treepos * 2, from, to);
			update(mid + 1, right, treepos * 2 + 1, from, to);
			tree[treepos] = tree[treepos * 2] + tree[treepos * 2 + 1];
		}
	}
};

struct Edge {
	int a, b, c, d;
	Edge(void) { a = b = c = d = 0; }
	Edge(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d) {}
};

int n;
vector<Edge> edgelist;
vector<vector<int> > graph, hld;
vector<segTree> thld;
vector<int> hld_num;
int childcnt[200001], height[200001], parent[200001][19];

void init(void);
void hld_init(void);
void hld_update(int a, int b);
int edge_num(int a, int hnum);
void rec_update(int p, int x);
int lca(int a, int b);
void precalc(void);

int main(void) {
	scanf("%d", &n);
	int i, a, b, c, d;
	graph.resize(n + 1);
	hld_num.resize(n + 1, -1);
	for (i = 0; i < n - 1; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		edgelist.push_back(Edge(a, b, c, d));
		graph[a].push_back(b);
		graph[b].push_back(a);
		// printf("connected %d - %d\n", a, b);
	}
	init();
	// printf("init finished\n");
	hld_init();
	// printf("hld_init finished\n");
	precalc();
	// printf("precalc finished\n");

	ll ans = 0;
	for (auto k : edgelist) {
		int a, b, hnum;
		if (height[k.a] < height[k.b]) { a = k.a; b = k.b; }
		else { a = k.b; b = k.a; }
		hnum = hld_num[b];
		int cnt = thld[hnum].tree[thld[hnum].sz + edge_num(b, hnum) - 1];
		// printf("cnt[%d ~ %d]: %d\n", a, b, cnt);
		if (!cnt) continue;
		if (k.c * cnt <= k.d) {
			ans += cnt * k.c;
		}
		else {
			ans += k.d;
		}
	}
	printf("%lld", ans);
	return 0;
}

void init(void) {
	queue<int> q;
	stack<int> st;
	q.push(1);
	st.push(1);
	height[1] = 1;
	while (!q.empty()) {
		int top = q.front();
		q.pop();
		for (auto k : graph[top]) {
			if (parent[top][0] == k) continue;
			parent[k][0] = top;
			// printf("parent[%d][0]: %d\n", k, top);
			height[k] = height[top] + 1;
			q.push(k);
			st.push(k);
		}
	}
	while (!st.empty()) {
		int top = st.top();
		st.pop();
		childcnt[top]++;
		childcnt[parent[top][0]] += childcnt[top];
	}
	for (int i = 1; i <= 18; i++) {
		for (int j = 1; j <= n; j++) {
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
		}
	}
}

void hld_init(void) {
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int top = q.front();
		// printf("top: %d\n", top);
		q.pop();
		for (auto k : graph[top]) {
			// printf("found: %d\n", k);
			if (parent[top][0] == k) continue;
			// printf("q.push(%d)\n", k);
			q.push(k);
		}
		if (top == 1) continue;
		int par = parent[top][0];
		if (childcnt[top] * 2 >= childcnt[par] && par != 1) {
			int hnum = hld_num[par];
			hld_num[top] = hnum;
			hld[hnum].push_back(top);
		}
		else {
			int hnum = (int)hld.size();
			hld.push_back(vector<int>(2));
			hld.back()[0] = par;
			hld.back()[1] = top;
			hld_num[top] = hnum;
		}
		// printf("hld_num[%d]: %d\n", top, hld_num[top]);
	}
	for (int i = 0; i < (int)hld.size(); i++) {
		thld.push_back(segTree());
		thld.back().init((int)hld[i].size() - 1);
	}
}

void precalc(void) {
	for (int i = 2; i <= n; i++) {
		// i - 1 -> i
		hld_update(i - 1, i);
	}
	for (int i = 0; i < (int)hld.size(); i++) thld[i].updateAll(1, thld[i].sz, 1);
}

int lca(int a, int b) {
	if (height[a] < height[b]) swap(a, b);
	for (int i = 18; i >= 0; i--) {
		if (height[a] - height[b] >= (1 << i)) a = parent[a][i];
	}
	if (a == b) return a;
	for (int i = 18; i >= 0; i--) {
		if (parent[a][i] != parent[b][i]) {
			a = parent[a][i];
			b = parent[b][i];
		}
	}
	return parent[a][0];
}

void hld_update(int a, int b) {
	// printf("hld_update(%d, %d)\n", a, b);
	int c = lca(a, b);
	// printf("lca found\n");
	rec_update(c, a);
	rec_update(c, b);
}

void rec_update(int p, int x) {
	// printf("rec_update(%d, %d)\n", p, x);
	// printf("hld_num: (%d, %d), (%d, %d)\n", p, hld_num[p], x, hld_num[x]);
	while (p != x) {
		if (hld_num[p] == hld_num[x]) {
			// printf("here\n");
			int hnum = hld_num[x];
			int from = edge_num(p, hnum) + 1;
			int to = edge_num(x, hnum);
			// printf("update: [%d, %d]\n", from, to);
			// printf("thld[%d].update(%d, %d)\n", hnum, from, to);
			thld[hnum].update(1, thld[hnum].sz, 1, from, to);
			return;
		}

		int hnum = hld_num[x];
		int to = edge_num(x, hnum);
		// printf("thld[%d].update(1, %d)\n", hnum, to);
		thld[hnum].update(1, thld[hnum].sz, 1, 1, to);
		x = hld[hnum][0];
	}
}

int edge_num(int a, int hnum) {
	int top = hld[hnum][0];
	return height[a] - height[top];
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:92:7: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   int a, b, hnum;
       ^
putovanje.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
putovanje.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 65