oj.uz

Submission #206168

# Submission time Handle Problem Language Result Execution time Memory
206168 2020-03-02T15:25:56 Z luciocf Putovanje (COCI20_putovanje) C++14
0 / 110
 483 ms 42460 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 2e5+10;

int n;
ll ans;

int tab[maxn][20], nivel[maxn];

int val[maxn];

vector<int> grafo[maxn];
map<pii, int> c1, c2;

void dfs(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v != p)
		{
			nivel[v] = nivel[u]+1, tab[v][0] = u;
			dfs(v, u);
		}
	}
}

void build(void)
{
	for (int j = 1; j < 20; j++)
		for (int i = 1; i <= n; i++)
			tab[i][j] = tab[tab[i][j-1]][j-1];
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = 19; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i];

	if (u == v) return u;

	for (int i = 19; i >= 0; i--)
		if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
			u = tab[u][i], v = tab[v][i];

	return tab[u][0];
}

int solve(int u, int p)
{
	int tot = val[u];

	for (auto v: grafo[u])
		if (v != p)
			tot += solve(v, u);

	if (u != 1)
	{
		if (1ll*tot*c1[{u, p}] > c2[{u, p}])
			ans += 1ll*c2[{u, p}];
		else
			ans += 1ll*tot*c1[{u, p}];
	}
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i < n; i++)
	{
		int u, v, a, b;
		scanf("%d %d %d %d", &u, &v, &a, &b);

		grafo[u].push_back(v), grafo[v].push_back(u);
		c1[{u, v}] = c1[{v, u}] = a, c2[{u, v}] = c2[{v, u}] = b;
	}

	dfs(1, 0); build();

	for (int i = 1; i < n; i++)
	{
		val[i]++, val[i+1]++;
		val[lca(i, i+1)] -= 2;
	}

	solve(1, 0);

	printf("%lld\n", ans);
}

Compilation message

putovanje.cpp: In function 'int solve(int, int)':
putovanje.cpp:71:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
putovanje.cpp: In function 'int main()':
putovanje.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
putovanje.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &u, &v, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 12 ms 5624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 483 ms 42460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 12 ms 5624 KB Output isn't correct
3 Halted 0 ms 0 KB -