제출 #223191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223191		oolimry	Putovanje (COCI20_putovanje)	C++14	110 / 110	125 ms	18912 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;
static vector<int> adj[100005];
static int heavy[100005];
static int depth[100005];
static int head[100005];
static int p[100005];
static int pos[100005];
static int sz[100005];
int cnt = 0; ///set to 1 if you're using fenwick tree

void dfs(int u){
    sz[u] = 1;
    int maxChild = 0;
    for(int v : adj[u]){
        if(sz[v] == 0){
            depth[v] = depth[u] + 1;
            dfs(v);
            sz[u] += sz[v];
            p[v] = u;
            if(sz[v] > maxChild){
                maxChild = sz[v];
                heavy[u] = v;
            }
        }
    }
}

void decompose(int u, int h){
    head[u] = h;
    pos[u] = cnt;
    cnt++;
    if(heavy[u] != 0) decompose(heavy[u], h);
    for(int v : adj[u]){
        if(sz[v] < sz[u] && v != heavy[u]){
            decompose(v,v);
        }
    }
}

struct edge{
	long long u, v, c1, c2; 
};

long long tree[400005];

int n; 
void rupdate(int l, int r, long long x){
	for(l += n, r += n;l < r;l >>= 1, r >>= 1){
		if(l&1){
			tree[l] += x;
			l++;
		}
		if(r&1){
			r--;
			tree[r] += x;
		}
	}
}
long long pquery(int i){
	long long res = 0;
	for(i += n;i > 0;i >>= 1) res += tree[i];
	return res;
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	vector<edge> edges;
	
	cin >> n;
	for(int i = 0;i < n-1;i++){
		int u, v, c1, c2;
		cin >> u >> v >> c1 >> c2; u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back({u,v,c1,c2});
	}
	
	dfs(0);
	decompose(0,0);
	
	for(int i = 0;i < n-1;i++){
		int a = i; int b = i + 1;
		if(depth[a] > depth[b]) swap(a,b);
		for(;head[a] != head[b];b = p[head[b]]){
			if(depth[head[a]] > depth[head[b]]) swap(a,b);
			rupdate(pos[head[b]],pos[b] + 1, 1);
			///any update and query affects pos[head[b]] inclusive to pos[b] inclusive
		}
		if(depth[a] > depth[b]) swap(a,b);
		rupdate(pos[a] + 1,pos[b] + 1, 1);
		///any update and query affects pos[a]+1 inclusive to pos[b] inclusive
	}
	
	long long ans = 0;
	for(edge e : edges){
		if(depth[e.u] < depth[e.v]) swap(e.u,e.v);
		long long cost = min(e.c2, pquery(pos[e.u]) * e.c1);
		ans += cost;
		//cout << e.u << " " << e.v << " " << cost << "\n";
	}
	cout << ans;
}

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