Submission #223196

#	Time	Username	Problem	Language	Result	Execution time	Memory
223196		shenxy	Putovanje (COCI20_putovanje)	C++11	110 / 110	249 ms	19960 KiB

putovanje

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> ii;
int N, depth[100000], st[100000], parent[100000], hchild[100000], head[100000], preo[100000], post[100000], cnt = 0;
vector<int> adjlist[100000];
int dfs1(int v) {
	int ms = 0;
	for (int i: adjlist[v]) {
		if (i == parent[v]) continue;
		depth[i] = depth[v] + 1;
		parent[i] = v;
		int temp = dfs1(i);
		st[v] += temp;
		if (temp > ms) ms = temp, hchild[v] = i;
	}
	return st[v];
}
void dfs2(int v) {
	preo[cnt] = v;
	post[v] = cnt++;
	if (hchild[v] != -1) {
		head[hchild[v]] = head[v];
		dfs2(hchild[v]);
	}
	for (int i: adjlist[v]) {
		if (i == parent[v]) continue;
		if (i == hchild[v]) continue;
		head[i] = i;
		dfs2(i);
	}
}
struct Fenwick {
	int s;
	vector<int> f;
	Fenwick(int N) {
		s = N;
		f = vector<int>(s + 1);
	}
	void update(int i, int v) {
		for (; i <= s; i += i & -i) f[i] += v;
	}
	int query(int a) {
		int ans = 0;
		for (; a > 0; a -= a & -a) ans += f[a];
		return ans;
	}
};
int main() {
	int A, B, C, D;
	scanf("%d", &N);
	map<ii, ii> edges;
	for (int i = 1; i < N; ++i) {
		scanf("%d %d %d %d", &A, &B, &C, &D);
		adjlist[A - 1].push_back(B - 1);
		adjlist[B - 1].push_back(A - 1);
		edges[ii(min(A - 1, B - 1), max(A - 1, B - 1))] = ii(C, D);
	}
	depth[0] = head[0] = 0, parent[0] = -1;
	fill_n(st, N, 1);
	fill_n(hchild, N, -1);
	dfs1(0);
	dfs2(0);
	Fenwick f(N);
	for (int i = 1; i < N; ++i) {
		A = i - 1, B = i;
		for (; head[A] != head[B]; B = parent[head[B]]) {
			if (depth[head[B]] < depth[head[A]]) swap(A, B);
			f.update(post[B] + 2, -1);
			f.update(post[head[B]] + 1, 1);
		}
		if (depth[B] < depth[A]) swap(A, B);
		f.update(post[A] + 2, 1);
		f.update(post[B] + 2, -1);
	}
	long long ans = 0;
	for (pair<ii, ii> i: edges) {
		A = i.first.first, B = i.first.second, C = i.second.first, D = i.second.second;
		if (depth[B] < depth[A]) swap(A, B);
		ans += min((long long) C * (long long) f.query(post[B] + 1), (long long) D);
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
putovanje.cpp:56: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: 25 / 25
• Subtask 3: 65 / 65