Submission #878339

#	Time	Username	Problem	Language	Result	Execution time	Memory
878339		hazzu	Putovanje (COCI20_putovanje)	C++17	110 / 110	80 ms	25528 KiB

putovanje

#include <bits/stdc++.h>
#define taskname "A"
using namespace std;

typedef long long ll;
struct Edge {
    int v, c1, c2;
};

class LowestCommonAncestor {
private:
    struct Node { 
        int depth, label;
        Node *parent, *jump;

        Node() {}
        Node(Node *p) {
            parent = p;
            depth = p->depth + 1;
            if (p->depth - p->jump->depth 
                == p->jump->depth - p->jump->jump->depth) {
                jump = p->jump->jump;
            }
            else jump = p; 
        }
    };

    int n;
    vector<Node*> t;
    vector<vector<int>> adj;

public:
    LowestCommonAncestor(int n): n(n), t(n + 1), adj(n + 1) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
    }

    void build() {
        t[1] = new Node();
        t[1]->depth = 0;
        t[1]->jump = t[1];
        t[1]->parent = nullptr;
        t[1]->label = 1;
        dfs(1, 1);
    }

    void dfs(int u, int p) {
        for (int v: adj[u]) if (v != p) {
            t[v] = new Node(t[u]);
            t[v]->label = v;
            dfs(v, u);
        }
    }

    int find(int u, int d) {
        Node *pu = t[u];
        while (pu->depth > d) {
            if (pu->jump->depth < d) 
                pu = pu->parent;
            else 
                pu = pu->jump;
        }
        return pu->label;
    }

    int get(int u, int v) {
        if (t[u]->depth < t[v]->depth) swap(u, v);
        u = find(u, t[v]->depth);
        Node *pu = t[u], *pv = t[v];
        
        while (pu != pv) {
            if (pu->jump == pv->jump) {
                pu = pu->parent;
                pv = pv->parent;
            }
            else {
                pu = pu->jump;
                pv = pv->jump;
            }
        }

        return pu->label;
    }
};

void Input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

void Solve() {
    int n; cin >> n;

    vector<vector<Edge>> adj(n + 1);
    LowestCommonAncestor lca(n);
    
    for (int i = 1; i < n; i++) {
        int u, v, c1, c2; 
        cin >> u >> v >> c1 >> c2;
        lca.add_edge(u, v);
        lca.add_edge(v, u);
        adj[u].push_back({v, c1, c2});
        adj[v].push_back({u, c1, c2});
    }
    lca.build();

    vector<ll> freq(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        int l = lca.get(i - 1, i);
        freq[i - 1]++;
        freq[i]++;
        freq[l] -= 2;
    }

    ll ans = 0;
    function<void(int, int)> dfs = [&](int u, int p) {
        for (Edge &e: adj[u])
            if (e.v != p) {
                dfs(e.v, u);
                ans += min(freq[e.v] * e.c1, e.c2 * 1ll);
                freq[u] += freq[e.v];
            }
    };
    dfs(1, 1);

    cout << ans;
}

int main(){
    clock_t begin = clock();
    Input();
    Solve();
    cerr << "Time: " << (clock() - begin + 1.0) / CLOCKS_PER_SEC << "s";
    return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'void Input()':
putovanje.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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