Submission #712937

#	Time	Username	Problem	Language	Result	Execution time	Memory
712937		iskhakkutbilim	Putovanje (COCI20_putovanje)	C++14	110 / 110	428 ms	46612 KiB

putovanje

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

#define ff first
#define ss second
#define int long long
#define all(a) a.begin(), a.end()
const int N = 2e5;
const int LOG = 20;
int up[N+1][LOG+1], depth[N+1];
int tin[N+1], tout[N+1];
int bigchild[N+1], chain[N+1], pos[N];
int sub[N+1];
vector<pair<int, int> > g[N+1];




int n, q, T, position;
void dfs(int v, int p){
	tin[v] = ++T;
	up[v][0] = p;
	for(int j = 1;j < LOG; j++) up[v][j] = up[up[v][j-1]][j-1];
	sub[v] = 1;
	int big=-1;
	for(auto [to, w] : g[v]){
		if(to != p){
			depth[to] = depth[v]+1;
			dfs(to, v);
			sub[v]+= sub[to];
			if(big == -1 or sub[big] < sub[to]){
				big = to;
			}
		}
	}
	tout[v] = ++T;
	bigchild[v] = big;
}
int isAnc(int v, int p){
	return (tin[p] <= tin[v] and tout[v] <= tout[p]);
}
void decompose(int v, int head){
	pos[v] = ++position;
	chain[v] = head;
	if(bigchild[v] != -1){
		decompose(bigchild[v], head);
	}
	for(auto [to, w] : g[v]){
		if(to == up[v][0] or to == bigchild[v]) continue;
		decompose(to, to);
	}
}
int tree[4*N], lazy[4*N];
void push(int v, int vl, int vr){
	if(lazy[v] == 0) return;
	tree[v]+= lazy[v];
	if(vl != vr){
		lazy[v<<1]+= lazy[v];
		lazy[v<<1|1]+= lazy[v];
	}
	lazy[v] = 0;
}

void add(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	if(l <= vl and r >= vr){
		lazy[v]+= x;
		push(v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	add(l, r, x, v<<1, vl, mid);
	add(l, r, x, v<<1|1, mid+1, vr);
	tree[v] = max(tree[v<<1], tree[v<<1|1]);
}

int get(int pos, int v, int vl, int vr){
	push(v, vl, vr);
	if(vl == vr) return tree[v];
	int mid = (vl + vr)>>1;
	if(mid >= pos) return get(pos, v<<1, vl, mid);
	else return get(pos, v<<1|1, mid+1, vr);
}


void query(int a, int b){
	for(; chain[a] != chain[b]; ){
		if(depth[b] < depth[a]) swap(a, b);
		add(min(pos[b], pos[chain[b]]), max(pos[b], pos[chain[b]]), 1, 1, 1, n);
		b = up[chain[b]][0];
	}	
	if(depth[b] < depth[a]) swap(a, b);
	add(min(pos[a], pos[b]), max(pos[a], pos[b]), 1, 1, 1, n);
}

int lca(int a, int b){
	if(depth[a] > depth[b]) swap(a, b);
	int k =depth[b]-depth[a];
	for(int i = 0;i < LOG; i++){
		if(k&(1LL<<i)){
			b = up[b][i];
		}
	}
	if(a == b) return a;
	for(int i = LOG-1; i >= 0; i--){
		if(up[a][i] != up[b][i]){
			a = up[a][i], b = up[b][i];
		}
	}
	return up[a][0];
}
main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	vector<int> A(n), B(n), C(n), C1(n);
	for(int i = 0;i < n-1; i++){
		int a, b; cin >> a >> b;
		A[i] = a, B[i] = b;
		cin >> C[i] >> C1[i];
		g[a].push_back({b, 0});
		g[b].push_back({a, 0});
	}
	dfs(1, 1);
	decompose(1, 1);
	for(int i = 1;i < n; i++){
		int u = i, v = i+1;
		int lc = lca(u, v);
		query(u, lc);
		query(v, lc);
		add(pos[lc], pos[lc], -2, 1, 1, n);
	}
	int sum = 0;
	for(int i = 0;i < n-1; i++){
		int cnt = 0;
		if(isAnc(A[i], B[i])){
			cnt = get(pos[A[i]], 1, 1, n);
		}else{
			cnt = get(pos[B[i]], 1, 1, n);
		}
		sum += min(C1[i], C[i] * cnt);
//		cout << A[i] << ' ' << B[i] << " = " << cnt << '\n';
	}
	cout << sum;
	return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'void dfs(long long int, long long int)':
putovanje.cpp:26:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |  for(auto [to, w] : g[v]){
      |           ^
putovanje.cpp: In function 'void decompose(long long int, long long int)':
putovanje.cpp:48:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |  for(auto [to, w] : g[v]){
      |           ^
putovanje.cpp: At global scope:
putovanje.cpp:113:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  113 | main(){
      | ^~~~

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