oj.uz

Submission #712937

# Submission time Handle Problem Language Result Execution time Memory
712937 2023-03-20T14:07:39 Z iskhakkutbilim Putovanje (COCI20_putovanje) C++14
110 / 110
 428 ms 46612 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 8 ms 5688 KB Output is correct
3 Correct 7 ms 5688 KB Output is correct
4 Correct 7 ms 5716 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 6 ms 5588 KB Output is correct
9 Correct 7 ms 5716 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 41252 KB Output is correct
2 Correct 271 ms 42800 KB Output is correct
3 Correct 296 ms 46516 KB Output is correct
4 Correct 299 ms 46612 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 281 ms 40500 KB Output is correct
7 Correct 155 ms 29872 KB Output is correct
8 Correct 274 ms 41548 KB Output is correct
9 Correct 190 ms 43404 KB Output is correct
10 Correct 163 ms 42296 KB Output is correct
11 Correct 225 ms 45132 KB Output is correct
12 Correct 212 ms 45300 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 8 ms 5688 KB Output is correct
3 Correct 7 ms 5688 KB Output is correct
4 Correct 7 ms 5716 KB Output is correct
5 Correct 6 ms 5716 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 6 ms 5588 KB Output is correct
9 Correct 7 ms 5716 KB Output is correct
10 Correct 265 ms 41252 KB Output is correct
11 Correct 271 ms 42800 KB Output is correct
12 Correct 296 ms 46516 KB Output is correct
13 Correct 299 ms 46612 KB Output is correct
14 Correct 3 ms 5332 KB Output is correct
15 Correct 281 ms 40500 KB Output is correct
16 Correct 155 ms 29872 KB Output is correct
17 Correct 274 ms 41548 KB Output is correct
18 Correct 190 ms 43404 KB Output is correct
19 Correct 163 ms 42296 KB Output is correct
20 Correct 225 ms 45132 KB Output is correct
21 Correct 212 ms 45300 KB Output is correct
22 Correct 428 ms 40304 KB Output is correct
23 Correct 389 ms 36780 KB Output is correct
24 Correct 427 ms 39680 KB Output is correct
25 Correct 6 ms 5460 KB Output is correct
26 Correct 173 ms 21288 KB Output is correct
27 Correct 341 ms 35392 KB Output is correct
28 Correct 164 ms 39256 KB Output is correct
29 Correct 204 ms 45440 KB Output is correct
30 Correct 202 ms 44816 KB Output is correct
31 Correct 8 ms 5636 KB Output is correct