oj.uz

Submission #218236

# Submission time Handle Problem Language Result Execution time Memory
218236 2020-04-01T15:24:55 Z sunho0371 Putovanje (COCI20_putovanje) C++14
110 / 110
 255 ms 28432 KB 
#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 ((ll)k.c * cnt <= (ll)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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 7 ms 940 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 15976 KB Output is correct
2 Correct 222 ms 17660 KB Output is correct
3 Correct 231 ms 18216 KB Output is correct
4 Correct 254 ms 21352 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 203 ms 17512 KB Output is correct
7 Correct 132 ms 12652 KB Output is correct
8 Correct 223 ms 18920 KB Output is correct
9 Correct 137 ms 20200 KB Output is correct
10 Correct 123 ms 19688 KB Output is correct
11 Correct 133 ms 21096 KB Output is correct
12 Correct 139 ms 21352 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 7 ms 940 KB Output is correct
10 Correct 208 ms 15976 KB Output is correct
11 Correct 222 ms 17660 KB Output is correct
12 Correct 231 ms 18216 KB Output is correct
13 Correct 254 ms 21352 KB Output is correct
14 Correct 6 ms 512 KB Output is correct
15 Correct 203 ms 17512 KB Output is correct
16 Correct 132 ms 12652 KB Output is correct
17 Correct 223 ms 18920 KB Output is correct
18 Correct 137 ms 20200 KB Output is correct
19 Correct 123 ms 19688 KB Output is correct
20 Correct 133 ms 21096 KB Output is correct
21 Correct 139 ms 21352 KB Output is correct
22 Correct 255 ms 28432 KB Output is correct
23 Correct 211 ms 24932 KB Output is correct
24 Correct 241 ms 27876 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 90 ms 13032 KB Output is correct
27 Correct 193 ms 23780 KB Output is correct
28 Correct 107 ms 18024 KB Output is correct
29 Correct 135 ms 21480 KB Output is correct
30 Correct 134 ms 20968 KB Output is correct
31 Correct 6 ms 640 KB Output is correct