Submission #530511

#	Time	Username	Problem	Language	Result	Execution time	Memory
530511		Servus2022	Putovanje (COCI20_putovanje)	C++14	20 / 110	1072 ms	26420 KiB

putovanje

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

typedef pair < int, int > PII;
typedef pair < PII, PII > Edge;

const int NMAX = 2e5 + 1, LOGMAX = 20;
const int ROOT = 1;

int N;
vector < int > G[NMAX];

vector < Edge > Edges;

int Euler[(NMAX << 1)], First[NMAX];
int Level[NMAX], father[NMAX];

int Log2[(NMAX << 1)];
int rmq[LOGMAX][(NMAX << 1)];

ll ans;

static inline int my_min (int a, int b)
{
    return ((a < b) ? a : b);
}

static inline int my_max (int a, int b)
{
    return ((a > b) ? a : b);
}

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for(int i = 1; i < N; ++i)
    {
        int a = 0, b = 0, c1 = 0, c2 = 0;
        cin >> a >> b >> c1 >> c2;

        G[a].push_back(b), G[b].push_back(a);

        Edges.push_back({{a, b}, {c1, c2}});
    }

    return;
}

static inline void DFS (int Node, int from = 0, int lvl = 0)
{
    Euler[++Euler[0]] = Node, First[Node] = Euler[0];
    Level[Node] = lvl, father[Node] = from;

    for(auto it : G[Node])
        if(it != from)
        {
            DFS(it, Node, lvl + 1);

            Euler[++Euler[0]] = Node;
        }

    return;
}

static inline void Build_RMQ ()
{
    Log2[1] = 0;
    for(int i = 2; i <= Euler[0]; ++i)
        Log2[i] = 1 + Log2[(i >> 1)];

    for(int i = 1; i <= Euler[0]; ++i)
        rmq[0][i] = Euler[i];

    for(int i = 1; i <= Log2[Euler[0]]; ++i)
        for(int j = 1; j <= Euler[0] - (1 << i) + 1; ++j)
            if(Level[rmq[i - 1][j]] < Level[rmq[i - 1][j + (1 << (i - 1))]])
                rmq[i][j] = rmq[i - 1][j];
            else
                rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];

    return;
}

static inline int Query (int left, int right)
{
    int lg = right - left + 1;
    lg = Log2[lg];

    if(Level[rmq[lg][left]] < Level[rmq[lg][right - (1 << lg) + 1]])
        return rmq[lg][left];

    return rmq[lg][right - (1 << lg) + 1];
}

static inline int LCA (int x, int y)
{
    if(x == y)
        return x;

    return Query(my_min(First[x], First[y]), my_max(First[x], First[y]));
}

static inline void Precalculation ()
{
    DFS(ROOT);

    Build_RMQ();

    return;
}

static inline void my_swap (int &x, int &y)
{
    x = (x ^ y), y = (x ^ y), x = (x ^ y);

    return;
}

int Mars[(NMAX << 1)];

static inline void Find_Solution ()
{
    for(auto it : Edges)
    {
        int x = it.first.first, y = it.first.second;
        int c1 = it.second.first, c2 = it.second.second;

        if(Level[x] > Level[y])
            my_swap(x, y);

        int cnts = Mars[y];

        if(1LL * cnts * c1 < 1LL * c2)
            ans += 1LL * cnts * c1;
        else
            ans += 1LL * c2;
    }

    cout << ans << '\n';

    return;
}

int main()
{
    Read();

    Precalculation();

    for(int i = 1; i < N; ++i)
    {
        int lca = LCA(i, i + 1);

        int x = i;
        while(x != lca)
            ++Mars[x], x = father[x];

        int y = i + 1;
        while(y != lca)
            ++Mars[y], y = father[y];
    }

    Find_Solution();

    return 0;
}

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