Submission #1276109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276109		chanhchuong123	Putovanje (COCI20_putovanje)	C++20	110 / 110	91 ms	21412 KiB

putovanje

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

const int MAX = 200020;
int n;
int h[MAX];
int dp[MAX];
int anc[18][MAX];
vector<int> adj[MAX];

struct Edge {
    int a, b, c, d;

    Edge(int _a = 0, int _b = 0, int _c = 0, int _d = 0) {
        a = _a;
        b = _b;
        c = _c;
        d = _d;
    }
} edges[MAX];

void dfs(int u, int p) {
    for (int v: adj[u]) if (v != p) {
        h[v] = h[u] + 1;
        anc[0][v] = u;
        for (int j = 1; j <= 17; ++j) {
            anc[j][v] = anc[j - 1][anc[j - 1][v]];
        }
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v); int k = h[u] - h[v];
    for (int j = 0; (1 << j) <= k; ++j) {
        if (k >> j & 1)
            u = anc[j][u];
    }
    if (u == v) return u;
    for (int j = 17; j >= 0; --j) {
        if (anc[j][u] != anc[j][v]) {
            u = anc[j][u];
            v = anc[j][v];
        }
    }
    return anc[0][u];
}

void reDfs(int u, int p) {
    for (int v: adj[u]) if (v != p) {
        reDfs(v, u);
        dp[u] += dp[v];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        edges[i] = Edge(a, b, c, d);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, -1);
    for (int i = 2; i <= n; ++i) {
        int p = lca(i - 1, i);
        dp[i - 1] += 1;
        dp[i] += 1;
        dp[p] -= 2;
    }
    reDfs(1, -1);
    long long ans = 0;
    for (int i = 1; i < n; ++i) {
        int a = edges[i].a, b = edges[i].b, c = edges[i].c, d = edges[i].d;
        if (h[a] > h[b]) swap(a, b); ans += min(1LL * dp[b] * c, 1LL * d);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

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

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