제출 #1185503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185503		kigdew	Putovanje (COCI20_putovanje)	C++20	110 / 110	58 ms	23036 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;

#define            ll    long long
#define           pair   pair<int,int>
template<class T> void   maximize(T& a,const T& b) {if (a < b) a = b;}
template<class T> void   minimize(T& a,const T& b) {if (a > b) a = b;}
template<class T>    T   PO2(T x) {return (1 << x);}
#define             fi   first
#define             sc   second
#define     mset(c, x)   memset(c, x, sizeof(c))
#define   __11HA7_KZ2__  signed main()

int dx[8] = {0, 1, 0,-1, 1, 1,-1,-1};
int dy[8] = {1, 0,-1, 0, 1,-1,-1, 1};

const int N = 2e5;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

int n;
int tin[N+15], tout[N+15], timer;
vector <pair> adj[N+15];
int up[20][N+15], egde_id[N+15];
ll sum[N+15];

struct Edge {
    int idx, c1, c2;
};
vector <Edge> edges;

void dfs1(int u, int p) {
    tin[u] = ++timer;
    up[0][u] = p;
    for (int k=1; k <= 17; k++) {
        up[k][u] = up[k-1][up[k-1][u]];
    }

    for (auto it : adj[u]) {
        int v = it.fi, idx = it.sc;
        if (v != p) {
            egde_id[idx] = v;
            dfs1(v, u);
        }
    }
    tout[u] = timer;
}

void dfs2(int u, int p) {
    for (auto it : adj[u]) {
        int v = it.fi;
        if (v != p) {
            dfs2(v, u);
            sum[u] += sum[v];
        }
    }
}

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] and tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;
    for (int k=17; k >= 0; k--) {
        if (!isAncestor(up[k][u], v)) {
            u = up[k][u];
        }
    }
    return up[0][u];
}

void update(int u, int v) {
    int lca_uv = lca(u, v);
    sum[u]++;
    sum[v]++;
    sum[lca_uv] -= 2;
}

 __11HA7_KZ2__
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i=1; i < n; i++) {
        int u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        edges.push_back({i, c1, c2});
    }

    dfs1(1, 1);
    for (int i=1; i < n; i++) {
        update(i, i+1);
    }
    dfs2(1, 1);

    ll ans = 0;
    for (auto it : edges) {
        int idx = it.idx, c1 = it.c1, c2 = it.c2;
        ans += min(sum[egde_id[idx]] * c1, 1ll * c2); 
    }
    cout << ans;
}

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