Submission #857788

#	Time	Username	Problem	Language	Result	Execution time	Memory
857788		caohung06	Putovanje (COCI20_putovanje)	C++17	0 / 110	69 ms	40528 KiB

putovanje

//  07-10-2023
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <time.h>
#include <assert.h>
#include <iomanip>
#include <cstring>
#include <queue>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define BIT(x, i) (1 & ((x) >> (i)))
#define OFF(x, i) ((x) ^ (1 << (i)))
#define ON(x, i) ((x) | (1 << (i)))
#define CNT(x) __builtin_popcountll(x)
#define file(name)                         \
    if (fopen(name ".inp", "r"))           \
    {                                      \
        freopen(name ".inp", "r", stdin);  \
        freopen(name ".out", "w", stdout); \
    }
#define faster                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
using namespace std;
const ll N = 200005;
ll n;
ll c[N], d[N], h[N], par[N][25], dp[N], cnt[N], s[N];
vector<pair<ll, ll>> a[N];
void dfs(ll u, ll p, ll t)
{
    h[u] = t;
    par[u][0] = p;
    for (auto v : a[u])
        if (v.ff != p)
            dfs(v.ff, u, t + 1);
}
ll lca(ll u, ll v)
{
    if (h[u] < h[v])
        swap(u, v);
    ll diff = h[u] - h[v];
    for (ll i = 20; i >= 0; i--)
        if (diff & (1 << i))
            u = par[u][i];
    if (u == v)
        return u;
    for (ll i = 20; i >= 0; i--)
        if (par[u][i] != par[v][i])
            u = par[u][i], v = par[v][i];
    return par[v][0];
}
void calc(ll u, ll p, ll id)
{
    for (auto x : a[u])
        if (x.ff != p)
            calc(x.ff, u, x.ff), dp[u] += dp[x.ff];
    dp[u] += s[u], cnt[id] = dp[u];
}
main()
{
    faster;
    file("tmp");
    cin >> n;
    ll u, v;
    for (ll i = 1; i < n; i++)
    {
        cin >> u >> v >> c[i] >> d[i];
        a[u].push_back({v, i}), a[v].push_back({u, i});
    }
    dfs(1, 0, 0);
    for (ll i = 1; (1 << i) <= n; i++)
        for (ll j = 1; j <= n; j++)
            par[j][i] = par[par[j][i - 1]][i - 1];
    for (ll i = 1; i < n; i++)
        s[i]++, s[i + 1]++, s[lca(i, i + 1)] -= 2;
    calc(1, 0, 0);
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
        ans += min(cnt[i] * c[i], d[i]);
    cout << ans;
}

Compilation message (stderr)

putovanje.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main()
      | ^~~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(name ".inp", "r", stdin);  \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:72:5: note: in expansion of macro 'file'
   72 |     file("tmp");
      |     ^~~~
putovanje.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(name ".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:72:5: note: in expansion of macro 'file'
   72 |     file("tmp");
      |     ^~~~

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