제출 #868875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
868875		pcc	Putovanje (COCI20_putovanje)	C++14	0 / 110	76 ms	32852 KiB

putovanje

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


struct Edge{
	ll cost[2];
	int to;
	Edge(){}
	Edge(int a,int b,int c){
		to = a,cost[0] = b,cost[1] = c;
	}
};

const int mxn = 2e5+10;
vector<Edge> tree[mxn];
int bit[mxn];
pll val[mxn];
ll add[mxn],del[mxn];
int dep[mxn],idx[mxn],link_top[mxn],sz[mxn],par[mxn],bs[mxn],cnt;
int n;

void modify(int p,int v){
	for(;p<mxn;p+=p&-p)bit[p] += v;
	return;
}
ll getval(int p){
	ll re= 0;
	for(;p>0;p-= p&-p)re += bit[p];
	return re;
}

void dfs1(int now){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt.to == par[now])continue;
		par[nxt.to] = now;
		dep[nxt.to] = dep[now]+1;
		val[nxt.to] = {nxt.cost[0],nxt.cost[1]};
		dfs1(nxt.to);
		if(!bs[now]||sz[bs[now]]<sz[nxt.to])bs[now] = nxt.to;
	}
	return;
}
void dfs2(int now,int top){
	link_top[now] = top;
	idx[now] = ++cnt;
	if(bs[now])dfs2(bs[now],top);
	for(auto nxt:tree[now]){
		if(nxt.to == bs[now]||nxt.to == par[now])continue;
		dfs2(nxt.to,nxt.to);
	}
	return;
}

void addval(int a,int b,int c){
	int ta = link_top[a],tb = link_top[b];
	while(ta != tb){
		if(dep[ta]<dep[tb]){
			swap(ta,tb);
			swap(a,b);
		}
		modify(idx[ta],c);
		modify(idx[a]+1,-c);
		a = par[ta];ta = link_top[a];
	}
	if(dep[a]>dep[b])swap(a,b);
	modify(idx[a],c);
	modify(idx[b]+1,-c);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<n;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		tree[a].push_back(Edge(b,c,d));
		tree[b].push_back(Edge(a,c,d));
	}
	par[1] = 0;
	dep[1] = 1;
	dfs1(1);
	dfs2(1,1);
	for(int i = 2;i<=n;i++){
		addval(i-1,i,1);
	}
	ll ans = 0;
	for(int i = 2;i<=n;i++){
		ans += min(getval(idx[i])*val[i].fs,val[i].sc);
	}
	cout<<ans;
}

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