Submission #209994

#	Time	Username	Problem	Language	Result	Execution time	Memory
209994		SamAnd	Putovanje (COCI20_putovanje)	C++17	110 / 110	200 ms	32760 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005;

int n;
vector<int> a[N];
vector<pair<int, int> > b[N];

int tin[N], tout[N], ti;
const int m = 19;
int p[N][m];

void dfs0(int x, int p0)
{
    tin[x] = ++ti;
    p[x][0] = p0;
    for (int i = 1; i < m; ++i)
        p[x][i] = p[p[x][i - 1]][i - 1];
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p0)
            continue;
        dfs0(h, x);
    }
    tout[x] = ti;
}

bool isp(int x, int y)
{
    return (tin[x] <= tin[y] && tin[y] <= tout[x]);
}

int lca(int x, int y)
{
    if (isp(x, y))
        return x;
    if (isp(y, x))
        return y;
    for (int i = m - 1; i >= 0; --i)
    {
        if (!isp(p[x][i], y))
            x = p[x][i];
    }
    return p[x][0];
}

long long ans;
int q[N];

void dfs(int x, int p)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        dfs(h, x);
        q[x] += q[h];
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
        {
            ans += min(b[x][i].second * 1LL, b[x][i].first * 1LL * q[x]);
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y, c1, c2;
        scanf("%d%d%d%d", &x, &y, &c1, &c2);
        a[x].push_back(y);
        a[y].push_back(x);
        b[x].push_back(m_p(c1, c2));
        b[y].push_back(m_p(c1, c2));
    }
    dfs0(1, 1);
    for (int i = 1; i < n; ++i)
    {
        int u = lca(i, i + 1);
        q[u] -= 2;
        q[i]++;
        q[i + 1]++;
    }
    dfs(1, 1);
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'void dfs0(int, int)':
putovanje.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
putovanje.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
putovanje.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &y, &c1, &c2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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