Submission #463494

#	Time	Username	Problem	Language	Result	Execution time	Memory
463494		Jasiekstrz	Putovanje (COCI20_putovanje)	C++17	110 / 110	228 ms	28396 KiB

putovanje

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int L=20;
const int PP=3e5;
int pot;
int tree[2*PP+10];
vector<pair<int,int>> e[N+10];
long long c[N+10][2];
int pre[N+10];
int post[N+10];
int d[N+10];
int jmp[N+10][L+2];
void dfs_pre(int x,int p)
{
	static int nr=0;
	pre[x]=++nr;
	d[x]=d[p]+1;
	jmp[x][0]=p;
	for(int l=1;l<=L;l++)
		jmp[x][l]=jmp[jmp[x][l-1]][l-1];
	for(auto [v,id]:e[x])
	{
		if(v==p)
			continue;
		dfs_pre(v,x);
	}
	post[x]=nr;
	return;
}
int lca(int x,int y)
{
	if(d[x]>d[y])
		swap(x,y);
	for(int l=L;l>=0;l--)
	{
		if(d[jmp[y][l]]>=d[x])
			y=jmp[y][l];
	}
	if(x==y)
		return x;
	for(int l=L;l>=0;l--)
	{
		if(jmp[x][l]!=jmp[y][l])
		{
			x=jmp[x][l];
			y=jmp[y][l];
		}
	}
	return jmp[x][0];
}
void add(int x,int cc)
{
	for(x+=pot-1;x>0;x/=2)
		tree[x]+=cc;
	return;
}
int read(int l,int r)
{
	int ans=0;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans+=tree[l++];
		if(r%2==0)
			ans+=tree[r--];
	}
	return ans;
}
long long dfs_ans(int x,int p)
{
	long long ans=0;
	for(auto [v,id]:e[x])
	{
		if(v==p)
			continue;
		ans+=dfs_ans(v,x);
		ans+=min(c[id][1],c[id][0]*read(pre[v],post[v]));
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b>>c[i][0]>>c[i][1];
		e[a].emplace_back(b,i);
		e[b].emplace_back(a,i);
	}
	dfs_pre(1,0);
	for(int i=1;i<n;i++)
	{
		add(pre[i],1);
		add(pre[i+1],1);
		add(pre[lca(i,i+1)],-2);
	}
	cout<<dfs_ans(1,0)<<"\n";
	return 0;
}

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