oj.uz

Submission #223202

# Submission time Handle Problem Language Result Execution time Memory
223202 2020-04-15T05:06:48 Z errorgorn Putovanje (COCI20_putovanje) C++14
110 / 110
 393 ms 54520 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 42616 KB Output is correct
2 Correct 43 ms 42744 KB Output is correct
3 Correct 43 ms 42872 KB Output is correct
4 Correct 45 ms 42880 KB Output is correct
5 Correct 44 ms 42744 KB Output is correct
6 Correct 41 ms 42616 KB Output is correct
7 Correct 43 ms 42616 KB Output is correct
8 Correct 44 ms 42744 KB Output is correct
9 Correct 44 ms 42872 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 52344 KB Output is correct
2 Correct 212 ms 53316 KB Output is correct
3 Correct 208 ms 54520 KB Output is correct
4 Correct 244 ms 54136 KB Output is correct
5 Correct 47 ms 42744 KB Output is correct
6 Correct 203 ms 52092 KB Output is correct
7 Correct 148 ms 49784 KB Output is correct
8 Correct 178 ms 52216 KB Output is correct
9 Correct 141 ms 52344 KB Output is correct
10 Correct 148 ms 52064 KB Output is correct
11 Correct 152 ms 52960 KB Output is correct
12 Correct 143 ms 52820 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 42616 KB Output is correct
2 Correct 43 ms 42744 KB Output is correct
3 Correct 43 ms 42872 KB Output is correct
4 Correct 45 ms 42880 KB Output is correct
5 Correct 44 ms 42744 KB Output is correct
6 Correct 41 ms 42616 KB Output is correct
7 Correct 43 ms 42616 KB Output is correct
8 Correct 44 ms 42744 KB Output is correct
9 Correct 44 ms 42872 KB Output is correct
10 Correct 181 ms 52344 KB Output is correct
11 Correct 212 ms 53316 KB Output is correct
12 Correct 208 ms 54520 KB Output is correct
13 Correct 244 ms 54136 KB Output is correct
14 Correct 47 ms 42744 KB Output is correct
15 Correct 203 ms 52092 KB Output is correct
16 Correct 148 ms 49784 KB Output is correct
17 Correct 178 ms 52216 KB Output is correct
18 Correct 141 ms 52344 KB Output is correct
19 Correct 148 ms 52064 KB Output is correct
20 Correct 152 ms 52960 KB Output is correct
21 Correct 143 ms 52820 KB Output is correct
22 Correct 393 ms 50424 KB Output is correct
23 Correct 334 ms 49528 KB Output is correct
24 Correct 344 ms 50424 KB Output is correct
25 Correct 43 ms 42744 KB Output is correct
26 Correct 138 ms 46200 KB Output is correct
27 Correct 255 ms 49276 KB Output is correct
28 Correct 118 ms 51192 KB Output is correct
29 Correct 139 ms 52832 KB Output is correct
30 Correct 148 ms 52856 KB Output is correct
31 Correct 45 ms 42872 KB Output is correct