제출 #1114268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114268		ljtunas	Putovanje (COCI20_putovanje)	C++14	110 / 110	132 ms	65252 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define Rep(i, n)  for(auto i{1}; i <= n; ++i)
#define For(i, a, b) for(auto i{a}; i <= (b); ++i)
#define Ford(i, a, b) for(auto i{a}; i >= (b); --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

#define name "friend"

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 1e6  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

int n, f[MAXN];
int depth[MAXN], p[MAXN][20], a[MAXN], b[MAXN], c1[MAXN], c2[MAXN];
vi G[MAXN];

void dfs(int u, int par) {
    p[u][0] = par;
    For (k, 1, 19) p[u][k] = p[p[u][k - 1]][k - 1];
    Forv (v, G[u]) {
        if (v == par) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int len = depth[u] - depth[v];
    For (k, 0, 19) if (Bit(len, k)) u = p[u][k];
    if (u == v) return u;
    Ford (k, 19, 0) {
        if (p[u][k] != p[v][k]) {
            u = p[u][k];
            v = p[v][k];
        }
    }
    return p[u][0];
}

void dfs0(int u, int par) {
    Forv(v, G[u]) {
        if (v == par) continue;
        dfs0(v, u);
        f[u] += f[v];
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //  freopen(name".inp", "r", stdin);
    //  freopen(name".out", "w", stdout);
    ////////////////////////////////
    cin >> n;
    For (i, 1, n - 1) {
        cin >> a[i] >> b[i] >> c1[i] >> c2[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    G[0].push_back(1);
    G[1].push_back(0);
    dfs(0, 0);
    For(i, 1, n - 1) {
        int LCA = lca(i, i + 1);
        f[i]++;
        f[i + 1]++;
        f[LCA]-=2;
    }

    int ans = 0;
    dfs0(1, 0);
    For(i, 1, n - 1) {
        if (depth[a[i]] < depth[b[i]]) swap(a[i], b[i]);
        ans += min(f[a[i]] * c1[i], c2[i]);
    }
    cout << ans << '\n';
    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}

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