제출 #1150009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150009		sitingfake	Putovanje (COCI20_putovanje)	C++20	110 / 110	97 ms	37232 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define int long long
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define off(x,i) (x&(~(1<<(i))))
#define on(x,i) (x(1<<(i)))
#define sitingfake 1
const int mod=1e9+7;
const long long linf=1e18+3;
const int inf=1e9;
const int maxarr=1e6+5;
const double pi=acos(-1);
int dx[]={0,1,-1,0};
int dy[]={1,0,0,-1};
const int maxn = 2e5+7;
int cnt[maxn];
int dp[maxn];
int par[maxn][20],depth[maxn],D[maxn];
vector<ii>a[maxn];
int ans;
int n;
struct edge
{
    int u;
    int v;
    int c1;
    int c2;
};
edge e[maxn];
void dfs(int u,int p)
{
    for(ii i:a[u])
    {
        int v=i.fi;
        int id=i.se;
        if(v==p) continue;
        par[v][0]=u;
        depth[v]=depth[u]+1;
        dfs(v,u);
    }
}
void prepare()
{
    for(int j=1;j<=19;j++)
    {
        for(int i=1;i<=n;i++)
        {
            par[i][j]=par[par[i][j-1]][j-1];
        }
    }
}
int lca(int u, int v)
{
    if (depth[u] < depth[v]) return lca(v, u);

    for (int i = 19; i >= 0; --i)
    {
        if (depth[par[u][i]] >= depth[v])
        {
            u = par[u][i];
        }
    }

    if (u == v) return u;

    for (int i = 19; i >= 0; --i)
    {
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];
}

void get(int u,int p,int id)
{
    for(ii i:a[u])
    {
        int v=i.fi;
        if(v!=p)
        {
            get(v,u,i.se);
            dp[u]+=dp[v];
        }
    }
    dp[u]+=D[u];
    if(id!=-1) cnt[id]=dp[u];
}
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   cin>>n;
   for(int i=1;i<n;i++)
   {
       int u,v,c1,c2;
       cin>>u>>v>>c1>>c2;
       a[u].push_back(ii(v,i));
       a[v].push_back(ii(u,i));
       e[i].c1=c1;
       e[i].c2=c2;
   }
   dfs(1,-1);
   prepare();
   depth[0]=-1;
   for(int i=1;i<n;i++)
   {
       D[i]++;
       D[i+1]++;
       int lc=lca(i,i+1);
       D[lc]-=2;
   }
   get(1,-1,-1);
   for(int i=1;i<n;i++)
   {
       int w1=e[i].c1;
       int w2=e[i].c2;
       ans+=min(cnt[i]*w1,w2);
   }
   cout<<ans;
   //execute;
}

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