Submission #1177547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177547		QuocSensei	Putovanje (COCI20_putovanje)	C++20	0 / 110	42 ms	23620 KiB

putovanje

#include <bits/stdc++.h>

#define ll long long
#define el cout << '\n'

using namespace std;

const int maxn = 1e5;
const int maxlog = 20;

struct Edge
{
    int x;
    ll s, h;
};

int n, beg[maxn + 10], fin[maxn + 10], timer = 0, par[maxn + 10][maxlog + 2];
ll light[maxn + 10], heavy[maxn + 10], ans = 0, cnt[maxn + 10];
vector<Edge> adj[maxn + 10];

void dfs(int top, int p = -1)
{
    beg[top] = ++timer;
    for (Edge e : adj[top])
    {
        int next_top = e.x;
        ll s = e.s;
        ll h = e.h;
        if (next_top == p) continue;
        dfs(next_top, top);
        cnt[top] += cnt[next_top];
        par[next_top][0] = top;
        light[next_top] = s;
        heavy[next_top] = h;
    }
    fin[top] = timer;
}
bool is_inside(int x, int y)
{
    if (!x) return 1;
    return beg[x] <= beg[y] && fin[y] <= fin[x];
}
int getLCA(int x, int y)
{
    if (is_inside(x, y)) return x;
    if (is_inside(y, x)) return y;
    for (int i = maxlog; i >= 0; i--)
        if (!is_inside(par[x][i], y))
            x = par[x][i];
    return par[x][0];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("PUTOVANJE.INP", "r"))
    {
        freopen("PUTOVANJE.INP", "r", stdin);
        freopen("PUTOVANJE.OUT", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        ll s, h;
        cin >> x >> y >> s >> h;
        adj[x].push_back({y, s, h});
        adj[y].push_back({x, s, h});
    }
    dfs(1);
    for (int i = 2; i <= n; i++)
    {
        cnt[i]++;
        cnt[i - 1]++;
        cnt[getLCA(i, i - 1)] -= 2;
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        ans += min(cnt[i] * light[i], heavy[i]);
    cout << ans;
}

Compilation message (stderr)

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

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