Submission #884033

#	Time	Username	Problem	Language	Result	Execution time	Memory
884033		mihtriii295	Putovanje (COCI20_putovanje)	C++17	110 / 110	113 ms	54376 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

/* Code by Nguyen Minh Tri (mihtriii) 12TT THPT Chuyen Ben Tre */

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

const ll MOD = 998244353;
const ll N = 2e5 + 10000;
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

ll a[N], b[N], c[N], d[N], h[N], res, par[20][N], n, f[N], fin[N];
vector<ll> adj[N];
map<pair<ll, ll>, ll> mp;

void DFS(ll u, ll p){
    for (ll v : adj[u]){
        if (v == p) continue;
        par[0][v] = u;
        h[v] = h[u] + 1;
        for (ll i = 1; i <= 17; ++i)
            par[i][v] = par[i - 1][par[i - 1][v]];
        DFS(v, u);
    }
}
void DFSin(ll u, ll p){
    fin[u] = f[u];
    for (ll v : adj[u]){
        if (v == p) continue;
        DFSin(v, u);
        fin[u] += fin[v];
    }
}

ll LCA(ll u, ll v){
    if (h[u] < h[v]) swap(u, v);
    ll delta = h[u] - h[v];
    for (ll i = 0; i <= 17; ++i){
        if ((delta >> i) & 1)
            u = par[i][u];
    }
    if (u == v) return u;
    for (ll i = 17; i >= 0; --i){
        if (par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][v];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    cout.tie(NULL);
    if(fopen("coci1920_r5_putovanje.inp", "r")){
        freopen("coci1920_r5_putovanje.inp", "r", stdin);
        freopen("coci1920_r5_putovanje.out", "w", stdout);
    }
    cin >> n;
    for (ll i = 1; i < n; ++i){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    DFS(1, 0);
    for (ll i = 2; i <= n; ++i){
        ll lca = LCA(i, i - 1);
        f[i]++;
        f[i - 1]++;
        f[lca] -= 2;
    }
    DFSin(1, 0);
    for (ll i = 1; i < n; ++i){
        int u = a[i], v = b[i];
        if (h[u] < h[v]) swap(u, v);
        res += min(fin[u] * c[i], d[i]);
    }
    cout << res;
    return 0;
}

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("coci1920_r5_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("coci1920_r5_putovanje.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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