제출 #805228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805228		vjudge1	Putovanje (COCI20_putovanje)	C++17	110 / 110	89 ms	36304 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
#define sws ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dbg(msg,x) cout<<msg<<" "<<x<<endl;
#define output(x) for(auto c:x){cout<<c<<" ";}cout<<" ";
#define int long long 
#define ff first
#define ss second
#define endl "\n"
#define pq priority_queue
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef vector<pair<int,int> > vpp;
const int MAXN = 2*1e5+1;
int up[MAXN][19];
int psum[MAXN];
int tin[MAXN];
int tout[MAXN]; 
int idx=0;
int ans=0;
int cur=0;

struct Edge{
    int dest;
    int c1;
    int c2;
    
    Edge(int a,int b,int c){
        dest=a;
        c1=b;
        c2=c;
    }

    Edge(){
        dest=c1=c2=0;
    }


};


vector<Edge> adj[MAXN];



void dfs(int v=1,int p=-1){

    up[v][0]=p;
    if(p==-1)up[v][0]=v;
    rep(i,1,19)up[v][i]=up[up[v][i-1]][i-1];

    tin[v]=idx++;
    for(auto c:adj[v]){
        if(c.dest == p)continue;
        dfs(c.dest,v);
    }

    tout[v]=idx++;
}


int getAns(int v=1,int p=-1){


    for(auto c:adj[v]){
        if(c.dest == p)continue;
        int aux = getAns(c.dest,v);
        ans+=min(aux*c.c1,c.c2);
        psum[v]+=aux;
    }


    return psum[v];
}

bool isAncestor(int a,int b){
    return tin[a]<=tin[b] && tout[a]>=tout[b];
}


int lca(int a,int b){
    if(isAncestor(a,b))return a;
    if(isAncestor(b,a))return b;

    rep(j,0,19){
        int i = 18-j;
        if(!isAncestor(up[a][i],b))a=up[a][i];
    }
    return up[a][0];
}
int32_t main(){
    sws
    int n;cin>>n;

    rep(i,0,n-1){
        int a,b,c1,c2;
        cin>>a>>b>>c1>>c2;
        adj[a].pb(Edge(b,c1,c2));
        adj[b].pb(Edge(a,c1,c2));
    }

    dfs();


    rep(i,1,n){
        psum[i]++;
        psum[i+1]++;
        psum[lca(i,i+1)]-=2;
    }


    getAns();

    cout<<ans;
    
}

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