Submission #350013

#	Time	Username	Problem	Language	Result	Execution time	Memory
350013		arnold518	Putovanje (COCI20_putovanje)	C++14	110 / 110	213 ms	30460 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e5;

struct Edge
{
	int u, v, p, q;
};

int N;
vector<Edge> adj[MAXN+10];

int par[MAXN+10][30], dep[MAXN+10];
int dp[MAXN+10];

void dfs(int now, int bef, int d)
{
	par[now][0]=bef;
	dep[now]=d;
	for(auto nxt : adj[now])
	{
		if(nxt.v==bef) continue;
		dfs(nxt.v, now, d+1);
	}
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[u]<=dep[par[v][i]]) v=par[v][i];
	if(u==v) return u;
	for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

ll ans;
void dfs2(int now, int bef, int p, int q)
{
	for(auto nxt : adj[now])
	{
		if(nxt.v==bef) continue;
		dfs2(nxt.v, now, nxt.p, nxt.q);
		dp[now]+=dp[nxt.v];
	}
	ans+=min((ll)dp[now]*p, (ll)q);
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++)
	{
		int u, v, p, q;
		scanf("%d%d%d%d", &u, &v, &p, &q);
		adj[u].push_back({u, v, p, q});
		adj[v].push_back({v, u, p, q});
	}

	dfs(1, 0, 1);
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	for(int i=1; i<N; i++)
	{
		int u=i, v=i+1, w=lca(u, v);
		dp[u]++; dp[v]++;
		dp[w]--; dp[w]--;
	}

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

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
putovanje.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d%d%d%d", &u, &v, &p, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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