Submission #1281069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281069		herominhsteve	Putovanje (COCI20_putovanje)	C++20	110 / 110	94 ms	24144 KiB

putovanje

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "PUTOVANJE"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 2e5 + 5;
const int LOG = 19;

struct Edges{
    int v;
    long long one,many;
    Edges(int V,long long O,long long ma):v(V),one(O),many(ma){}
};

int n;
vector<Edges> graph[MAXN];
vector<vector<int>> up;

void init(){
	cin>>n;
    up.assign(LOG+1,vector<int>(n+1,-1));
    for (int i=1;i<n;i++){
        int u,v,one,many;
        cin>>u>>v>>one>>many;
        graph[u].emplace_back(v,one,many);
        graph[v].emplace_back(u,one,many);
    }
}

namespace LCK{
    int timedfs;
    int in[MAXN],out[MAXN];
    
    void dfs(int u=1,int pre=-1){
        up[0][u] = pre;
        in[u] = ++timedfs;
        for (int k=1;k<=LOG;k++){
            if (~up[k-1][u]) up[k][u] = up[k-1][up[k-1][u]];
            else up[k][u] = -1;
        }
        for (const Edges &x : graph[u]){
            if (x.v ^ pre){
                dfs(x.v,u);
            }
        }
        out[u] = ++timedfs;
    }

    bool isAncestor(int u,int v){
        return (in[u] <= in[v] and out[u] >= out[v]);
    }

    int LCA(int u,int v){
        if (isAncestor(u,v)) return u;
        if (isAncestor(v,u)) return v;
        for (int k=LOG;k>=0;k--){
            if (~up[k][u] and !isAncestor(up[k][u],v)){
                u = up[k][u];
            }
        }
        return up[0][u];
    }

};

vector<long long> edgeUsed;

long long res = 0;

void dfs(int u=1,int pre=-1){
    for (const Edges &x : graph[u]){
        int v = x.v;
        long long many = x.many;
        long long once = x.one;
        if (v == pre) continue;
        dfs(v,u);
        res += min(edgeUsed[v] * once,many);
        edgeUsed[u] += edgeUsed[v];
    }
}

void sol(){
	LCK::dfs();
    edgeUsed.assign(n+1,0);
    for (int u=1;u<n;u++){
        edgeUsed[u]++;
        edgeUsed[u+1]++;
        edgeUsed[LCK::LCA(u,u+1)]-=2;
    }
    dfs();
    cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

putovanje.cpp: In function 'void setup()':
putovanje.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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