Submission #223199

#	Time	Username	Problem	Language	Result	Execution time	Memory
223199		dantoh000	Putovanje (COCI20_putovanje)	C++14	110 / 110	167 ms	16120 KiB

putovanje

///Heavy Light Decomposition
///Problem: cowland (USACO)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n,q;
int p[N], d[N], sz[N], h[N], pos[N], e[N];
int fw[N];
int A[N], B[N], C1[N], C2[N];
int v1[N], v2[N];
int ct = 1;
vector<int> adjlist[N];
void up(int x, int v){
    while (x < N){
        fw[x] += v;
        x += x&(-x);
    }
}
int query(int x){
    int res = 0;
    while (x){
        res += fw[x];
        x -= x&(-x);
    }
    return res;
}
void rangeadd(int s, int e){
    up(s,1);
    up(e+1,-1);
}
void dfs(int u){
	sz[u] = 1;
	for (auto v : adjlist[u]){
		if (p[v] == 0){
			p[v] = u;
			d[v] = d[u]+1;
			dfs(v);
			sz[u] += sz[v];
		}
	}
}
void decomp(int u){
	pos[u] = ct++;
	int heavy = 0;
	for (auto v : adjlist[u]){
		if (p[u] == v) continue;
		if (sz[heavy] < sz[v]) heavy = v;
	}
	if (heavy == 0) return;
	h[heavy] = h[u];
	decomp(heavy);
	for (auto v : adjlist[u]){
		if (v != heavy && v != p[u]) decomp(v);
	}
}




void add(int u, int v){
    //printf("adding on path %d->%d\n",u,v);
    int ans = 0;
	while (h[u] != h[v]){
        if (u == 0 || v == 0) break;;
        //printf("%d,%d\n",u,v);
		if (d[h[u]] > d[h[v]]) swap(u,v);
		//printf("moving from %d -> %d\n",pos[v],pos[h[v]]);
		rangeadd(pos[h[v]],pos[v]);
		v = p[h[v]];
	}
	if (d[u] > d[v]) swap(u,v);
	//printf("cur at %d %d\n",pos[u],pos[v]);
	rangeadd(pos[u]+1,pos[v]);
}
/*
int que(int u, int v){
	int ans = 0;
	while (h[u] != h[v]){
		if (u == 0 || v == 0) return 0;
		if (d[h[u]] > d[h[v]]) swap(u,v);
		ans ^= root->query(pos[h[v]],pos[v]);
		v = p[h[v]];
	}
	if (d[u] > d[v]) swap(u,v);
	ans ^= root->query(pos[u],pos[v]);
	return ans;
}*/
int main(){
	scanf("%d",&n);
	for (int i = 1; i < n; i++){
		scanf("%d%d%d%d",&A[i],&B[i],&C1[i],&C2[i]);
		adjlist[A[i]].push_back(B[i]);
		adjlist[B[i]].push_back(A[i]);
	}
	iota(h,h+N,0);
	p[1] = -1;
	dfs(1);
	decomp(1);
	for (int i =1 ; i<= n; i++){
        //printf("%d pos %d\n",i,pos[i]);
	}
	for (int i = 1; i < n; i++){
        if (d[A[i]] < d[B[i]]) swap(A[i],B[i]);
        //printf("edge %d: %d -> %d\n",A[i],B[i]);
	}
	for (int i = 1; i < n; i++){
		add(i,i+1);
	}
	ll ans = 0;
	for (int i = 1; i < n; i++){
        //printf("querying pos[%d] = %d\n",A[i],pos[A[i]]);
        int num = query(pos[A[i]]);
        //printf("edge connecting %d to %d has been used %d times\n",A[i],B[i],num);
        ans += min((ll)num*C1[i],(ll)C2[i]);
	}
	printf("%lld",ans);
}

Compilation message (stderr)

putovanje.cpp: In function 'void add(int, int)':
putovanje.cpp:63:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans = 0;
         ^~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
putovanje.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&A[i],&B[i],&C1[i],&C2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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