Submission #1136084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136084		pcheloveks	Putovanje (COCI20_putovanje)	C++20	110 / 110	115 ms	35276 KiB

putovanje

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;

const ll DIM = 200007;
const ll INF = 9999999999;
const ll mod = 1000000007; 
const ll BSIZE = 500;

class edge {
public:
    ll v2, c1, c2;
};

ll tin[DIM], tout[DIM], binJ[DIM][16], par[DIM];
ll c1[DIM], c2[DIM];
vector < edge > v[DIM];

ll n, m, timer, ans, q;

ll euler[DIM], p[DIM];

void dfs(ll val, ll prev) {
    tin[val] = ++timer;
    if (prev != val) {
        par[val] = prev;
    }

    binJ[val][0] = prev;
    for (int i = 1; i <= 15; i++) {
        binJ[val][i] = binJ[binJ[val][i - 1]][i - 1];
    }

    for (auto to : v[val]) {
        if (to.v2 != prev) {
            c1[to.v2] = to.c1;
            c2[to.v2] = to.c2;
            dfs(to.v2, val);
        }
    }
    tout[val] = ++timer;
}

bool upper(ll v1, ll v2) {
    //if (v1 == 0) return true;
    return ((tin[v1] <= tin[v2]) && (tout[v2] <= tout[v1]));
}

ll findLca(ll v1, ll v2) {
    if (upper(v1, v2)) return v1;
    if (upper(v2, v1)) return v2;

    for (int i = 15; i >= 0; i--) {
        if (!upper(binJ[v1][i], v2)) v1 = binJ[v1][i];
    }
    return binJ[v1][0];
}

void solve(ll t) {
    cin >> n;
    for (int i = 1; i < n; i++) {
        ll v1, v2, c1, c2;
        cin >> v1 >> v2 >> c1 >> c2;
        v[v1].push_back({ v2, c1, c2 });
        v[v2].push_back({ v1, c1, c2 });
    }
    timer = 0;
    dfs(1, 1);
    for (int i = 1; i < n; i++) {
        ll v1 = i;
        ll v2 = i + 1;
        ll val = 1;

        ll lca = findLca(v1, v2);
        euler[tin[v1]] += val;
        euler[tin[v2]] += val;
        euler[tin[lca]] -= 2 * val;
    }
    p[0] = 0;
    for (int i = 1; i <= 2 * n; i++) {
        p[i] = p[i - 1] + euler[i];
        euler[i] = 0;
    }
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        v[i].clear();
        ll val = p[tout[i]] - p[tin[i] - 1];
        if (val * c1[i] <= c2[i]) res += val * c1[i];
        else res += c2[i];
    }
    cout << res << endl;
    
}

int main() {

    solve(0);

    return 0;
}

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