제출 #223202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223202		errorgorn	Putovanje (COCI20_putovanje)	C++14	110 / 110	393 ms	54520 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

struct E{
	int node;
	
	int c1,c2;
	
	E(int a,int b,int c){
		node=a;
		c1=b,c2=c;
	}
};

int n;
vector<E> al[200005];
int in[200005]; //preorder
int out[200005]; //postorder
int st[200005]; //subtree size
int parent[200005]; //first parent
int hparent[200005]; //parent on heavy path
int depth[200005];
void dfs_st(int i,int p){
    parent[i]=p;
    st[i]=1;
    if (al[i][0].node==p && al[i].size()>1) swap(al[i][0],al[i][1]);
    for (auto &it:al[i]){ ///& is important here
        if (it.node==p) continue;
        depth[it.node]=depth[i]+1;
        dfs_st(it.node,i);
        st[i]+=st[it.node];
        if (st[it.node]>st[al[i][0].node]){
            swap(it,al[i][0]);
            //we ensure heavy child is al[i][0]
        }
    }
}

int dfs_time=0;
void dfs_hld(int i,int p){
    in[i]=dfs_time++;
    for (auto it:al[i]){
        if (it.node==p) continue;
        hparent[it.node]=(it.node==al[i][0].node)?hparent[i]:it.node;
        dfs_hld(it.node,i);
    }
    out[i]=dfs_time;
}

struct node{
  int s,e,m;
  long long val=0;
  node *l,*r;
  node(int _s,int _e){
    s=_s,e=_e,m=(s+e)>>1;
	
	if (s!=e){
    	l=new node(s,m);
    	r=new node(m+1,e);
	}
  }
  long long query(int i){
    if (s==e) return val;
	else if (i<=m) return val+l->query(i);
	else return val+r->query(i);
  }
  void update(int i, int j, long long k){
    if (s==i && e==j) val+=k;
	else if (j<=m) l->update(i,j,k);
	else if (m<i) r->update(i,j,k);
	else l->update(i,m,k),r->update(m+1,j,k);
  }
}*root=new node(0,400005);


void hld_update(int i,int j){
    while (hparent[i]!=hparent[j]){
        if (depth[hparent[i]]<depth[hparent[j]]) swap(i,j);
        root->update(in[hparent[i]],in[i],1);
        i=parent[hparent[i]];
    }
    if (in[i]>in[j]) swap(i,j);
    if (i!=j) root->update(in[i]+1,in[j],1);
}

ll C1[200005];
ll C2[200005];

void dfs(int i,int p){
	for (auto &it:al[i]){
		if (it.node==p) continue;
		
		C1[it.node]=it.c1;
		C2[it.node]=it.c2;
		
		dfs(it.node,i);
	}
}


int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n;
	
	int a,b,c,d;
	for (int x=1;x<n;x++){
		cin>>a>>b>>c>>d;
		al[a].push_back(E(b,c,d));
		al[b].push_back(E(a,c,d));
	}
	
	parent[1]=0;
	hparent[1]=1;
    dfs_st(1,-1);
    dfs_hld(1,-1);

	for (int x=1;x<n;x++) hld_update(x,x+1);
	
	dfs(1,-1);
	
	ll ans=0;
	//for (int x=1;x<=n;x++) cout<<root->query(in[x])<<" "<<C1[x]<<" "<<C2[x]<<endl;
	for (int x=2;x<=n;x++) ans+=min(root->query(in[x])*C1[x],C2[x]);
	
	cout<<ans<<endl;
}

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