oj.uz

Submission #799683

# Submission time Handle Problem Language Result Execution time Memory
799683 2023-07-31T20:08:14 Z vjudge1 Putovanje (COCI20_putovanje) C++17
25 / 110
 552 ms 95204 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define rep(i,a,b) for(int i=(int)(a); i < (int)(b); i++)

typedef long long ll;

using iiii = array<int, 4>;

const int oo = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5+2;

vector<vector<int>> g(MAXN);
map<pair<int,int>, int> cost_each, cost_free;
vector<int> tin(2*MAXN), tout(2*MAXN);
vector<vector<int>> up(MAXN, vector<int>(20));
int TIMER = 0;
vector<int> ans(MAXN, 0);
vector<int> cost_each_vertex(MAXN), cost_free_vertex(MAXN);
int res = 0;

void dfs(int u=0, int p=0) {
	tin[u] = TIMER++;

	cost_each_vertex[u] = cost_each[{u, p}];
	cost_free_vertex[u] = cost_free[{u, p}];

	up[u][0] = p;
	for(int i = 1; i < 20; i++)
		up[u][i] = up[up[u][i-1]][i-1];
	
	for(auto v: g[u]) if(v != p)
		dfs(v, u);

	tout[u] = TIMER++;

	/*
	cout << "---------- db -----------\n";
	cout << "u = " << u << endl;
	cout << "tin[u] = " << tin[u] << endl;
	cout << "set " << query(tin[u], tin[u]) << endl;
	cout << "tout[u] = " << tout[u] << endl;
	cout << "set " << query(tout[u], tout[u]) << endl;
	*/
}

int is_ancestor(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
	
	if(is_ancestor(u, v)) {
		ans[u]--;
		ans[v]++;
		return u;
	}

	if(is_ancestor(v, u)) {
		ans[v]--;
		ans[u]++;
		return v;
	}

	ans[u]++;
	ans[v]++;
	for(int i = 19; i >= 0; i--) {
		if(!is_ancestor(up[u][i], v))
			u = up[u][i];
	}
	ans[up[u][0]]--;
	return up[u][0];
}

void compute_ans(int u=1, int p=0) {
	for(auto v: g[u]) if(v != p) {
		compute_ans(v, u);
		ans[u] += ans[v];
	}
	res += min(ans[u]*cost_each_vertex[u], cost_free_vertex[u]);
}

void solve() {
	int n;
	cin >> n;
	vector<iiii> edges(n-1);

	for(auto& [a, b, c, d]: edges) {
		cin >> a >> b >> c >> d;
		g[a].push_back(b);
		g[b].push_back(a);
		cost_each[{a, b}] = c;
		cost_each[{b, a}] = c;
		cost_free[{a, b}] = d;
		cost_free[{b, a}] = d;
	}

	g[0].push_back(1);
	dfs();

	for(int i = 1; i+1 <= n; i++) {
		lca(i, i+1);
	}
	compute_ans();
	cout << res << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55128 KB Output is correct
2 Incorrect 30 ms 55696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 89560 KB Output is correct
2 Correct 340 ms 91152 KB Output is correct
3 Correct 391 ms 95080 KB Output is correct
4 Correct 552 ms 95204 KB Output is correct
5 Correct 33 ms 55272 KB Output is correct
6 Correct 452 ms 88580 KB Output is correct
7 Correct 271 ms 79532 KB Output is correct
8 Correct 394 ms 89660 KB Output is correct
9 Correct 201 ms 91568 KB Output is correct
10 Correct 188 ms 90432 KB Output is correct
11 Correct 202 ms 93396 KB Output is correct
12 Correct 214 ms 93640 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55128 KB Output is correct
2 Incorrect 30 ms 55696 KB Output isn't correct
3 Halted 0 ms 0 KB -