Submission #1101130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101130		InvMOD	Putovanje (COCI20_putovanje)	C++14	110 / 110	83 ms	39280 KiB

putovanje

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

#define fi first
#define se second
#define gcd __gcd
#define siz(v) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T &a, T b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T &a, T b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;
const int lg = 21;

struct Edge{
    int u,v;
    ll w1,w2;
};

int n, par[lg][N], val[N], h[N];
vector<int> adj[N];
Edge E[N];

void dfs(int x, int p)
{
    for(int v : adj[x])if(v != p){
        par[0][v] = x;
        h[v] = h[x] + 1;
        for(int i = 1; i < lg; i++) par[i][v] = par[i-1][par[i-1][v]];
        dfs(v, x);
    }
    return;
}

int get_LCA(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int k = h[u] - h[v];
    for(int i = 0; i < lg; i++){
        if(k>>i&1) u = par[i][u];
    }
    if(u == v) return v;
    for(int i = lg-1; i >= 0; i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][v];
}

void get_val(int x, int p){
    for(int v : adj[x])if(v != p){
        get_val(v, x);
        val[x] = val[x] + val[v];
    }
    return;
}

void solve()
{
    cin >> n;
    for(int i = 2; i <= n; i++){
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        adj[u].push_back(v);
        adj[v].push_back(u);
        E[i] = {u, v, w1, w2};
    }

    dfs(1, -1);

    for(int i = 2; i <= n; i++){
        val[i]++, val[i-1]++;
        val[get_LCA(i,i-1)] -= 2;
    }

    get_val(1, -1);

    ll answer = 0;
    for(int i = 2; i <= n; i++){
        int u = E[i].u, v = E[i].v;
        if(h[u] > h[v]) swap(u, v);
        answer = answer + min(E[i].w2, E[i].w1 * (1ll*val[v]));
    }

    cout << answer <<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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