Submission #206141

#	Time	Username	Problem	Language	Result	Execution time	Memory
206141		oko	Putovanje (COCI20_putovanje)	C++14	110 / 110	236 ms	41592 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,a[200050],b[200050],st[200050][30],dp[200050],num[200050],ans;
vector<pair<int,int> >gr[200050];
void cal(int x,int p)
{
    dp[x]=dp[p]+1;
    st[x][0]=p;
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first;
        if(u==p)continue;
        cal(u,x);
    }
}
int lca(int x,int y)
{
    if(dp[y]>dp[x])swap(x,y);
    int dif=dp[x]-dp[y];
    for(int i=0;i<23;i++)
    {
        if(dif&(1<<i))x=st[x][i];
    }
    if(x==y)return x;
    for(int i=23;i>=0;i--)
    {
        if(st[x][i]!=st[y][i])
        {
            x=st[x][i];
            y=st[y][i];
        }
    }
    return st[x][0];
}
void dfs(int x,int p)
{
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first;
        if(u==p)continue;
        dfs(u,x);
        num[x]+=num[u];
    }
}
void dfs1(int x,int p)
{
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first,in=gr[x][i].second;
        if(u==p)continue;
        if(a[in]*num[u]<=b[in])ans+=a[in]*num[u];
        else ans+=b[in];
        dfs1(u,x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        cin>>x>>y>>a[i]>>b[i];
        gr[x].push_back({y,i});
        gr[y].push_back({x,i});
    }
    cal(1,0);
    for(int i=1;i<=24;i++)
    {
        for(int j=1;j<=n;j++)st[j][i]=st[st[j][i-1]][i-1];
    }
    for(int i=1;i<n;i++)
    {
        int lc=lca(i,i+1);
        if(lc==i)
        {
            num[i+1]++;
            num[i]--;
        }
        else if(lc==i+1)
        {
            num[i]++;
            num[i+1]--;
        }
        else
        {
            num[i]++;
            num[i+1]++;
            num[lc]-=2;
        }
    }
    dfs(1,0);
    dfs1(1,0);
    cout<<ans;
}

Compilation message (stderr)

putovanje.cpp: In function 'void cal(int, int)':
putovanje.cpp:10:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~
putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~
putovanje.cpp: In function 'void dfs1(int, int)':
putovanje.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~

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