제출 #857793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857793		NguyenTN091106	Putovanje (COCI20_putovanje)	C++14	110 / 110	92 ms	28520 KiB

putovanje

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define mp(x,y) make_pair((x),(y))
#define bit(x,i) (((x)>>(i))&1)
#define MASK(i) (1<<(i))
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
const int maxn=2e5+5;
const ll oo=2e18+5;
const int MOD=1e9+7;
const int inf=1e9+7;
void init()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}
int n,c[2][maxn],pa[maxn][20],depth[maxn];
vector< pair<int,int> > adj[maxn];
void dfs(int u,int pre)
{
    for(int it=0;it<(int)adj[u].size();it++)
    {
        int v=adj[u][it].ff;
        if(v==pre) continue;
        depth[v]=depth[u]+1;
        pa[v][0]=u;
        for(int j=1;j<=18;j++) pa[v][j]=pa[pa[v][j-1]][j-1];
        dfs(v,u);
    }
}
int LCA(int u,int v)
{
    if(depth[u]<depth[v]) swap(u,v);
    for(int j=18;j>=0;j--) if(depth[u]-MASK(j)>=depth[v]) u=pa[u][j];
    if(u==v) return u;
    for(int j=18;j>=0;j--) if(pa[u][j]!=pa[v][j])
    {
        u=pa[u][j];
        v=pa[v][j];
    }
    return pa[u][0];
}
ll cnt[maxn],sum[maxn];
void calc(int u,int pre,int id)
{
    for(int it=0;it<(int)adj[u].size();it++)
    {
        int v=adj[u][it].ff,newId=adj[u][it].ss;
        if(v==pre) continue;
        calc(v,u,newId);
        cnt[u]+=cnt[v];
    }
    if(id) sum[id]=cnt[u];
}
void solve()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v>>c[0][i]>>c[1][i];
        adj[u].push_back(mp(v,i));
        adj[v].push_back(mp(u,i));
    }
    dfs(1,0);
    for(int i=1;i<n;i++)
    {
        int w=LCA(i,i+1);
        cnt[i]++;
        cnt[i+1]++;
        cnt[w]-=2;
    }
    calc(1,0,0);
    ll ans=0;
    for(int i=1;i<n;i++)
        ans+=min(1LL*c[0][i]*sum[i],1LL*c[1][i]);
    cout<<ans;
}
int main()
{
    init();
//    int t;
//    cin>>t;
//    while(t--)
        solve();
    return 0;
}

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