Submission #897472

#	Time	Username	Problem	Language	Result	Execution time	Memory
897472		Alora	Putovanje (COCI20_putovanje)	C++17	110 / 110	80 ms	27852 KiB

putovanje

#include <bits/stdc++.h>
#define Alora "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define all(v) v.begin(), v.end()
#define pb push_back
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int n, cnt[maxn], times[maxn], h[maxn], cha[maxn][20];
vector <pii> g[maxn];
pii c[maxn];

void dfs(int u, int fa){
    for(auto [v, id]: g[u]) if(v != fa){
        h[v] = h[u] + 1;
        cha[v][0] = u;
        fi(i, 1, 18) cha[v][i] = cha[cha[v][i - 1]][i - 1];
        dfs(v, u);
    }
}
int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    fi(i, 0, 18) if(getbit(d, i)) x = cha[x][i];
    if(x == y) return x;
    fid(i, 18, 0) if(cha[x][i] != cha[y][i]){
        x = cha[x][i];
        y = cha[y][i];
    }
    return cha[x][0];
}
void dfs_cal(int u, int fa){
    for(auto [v, id]: g[u]) if(v != fa){
        dfs_cal(v, u);
        times[id] = cnt[v];
        cnt[u] += cnt[v];
    }
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	if(fopen(Alora".inp", "r")){
    freopen(Alora".inp", "r", stdin);
    freopen(Alora".out", "w", stdout);}
    cin >> n;
    fi(i, 1, n - 1){
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        c[i] = {a, b};
        g[u].pb({v, i});
        g[v].pb({u, i});
    }
    dfs(1, 1);
    fi(u, 1, n - 1){
        int v = u + 1;
        int z = lca(u, v);
        cnt[u]++; cnt[v]++;
        cnt[z] -= 2;
    }
    dfs_cal(1, 1);
    ll res = 0;
    fi(i, 1, n - 1) res += min(1ll*times[i]*c[i].f, 1ll*c[i].se);
    cout << res;
    return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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