Submission #1124883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124883		sitingfake	Putovanje (COCI20_putovanje)	C++20	25 / 110	100 ms	36928 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 present[maxn];
int dp[maxn];
int par[maxn][22],depth[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;
        present[id]=v;
        par[v][0]=u;
        depth[v]=depth[u]+1;
        dfs(v,u);
    }
}
void prepare()
{
    for(int j=1;(1<<j)<=n;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]) swap(u,v);
    int diff=depth[u]-depth[v];
    for(int i=0;(1<<i)<=diff;i++)
    {
        if((diff>>i)&1)
            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)
{
    for(ii i:a[u])
    {
        int v=i.fi;
        if(v!=p)
        {
            get(v,u);
            dp[u]+=dp[v];
        }
    }
}
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]={u,v,c1,c2};
   }
   dfs(1,-1);
   prepare();
   for(int i=1;i<n;i++)
   {
       dp[i]++;
       dp[i+1]++;
       dp[lca(i,i+1)]-=2;
   }
   get(1,-1);
   for(int i=1;i<n;i++)
   {
       int c=present[i];
       int w1=e[i].c1;
       int w2=e[i].c2;
       ans+=min(dp[c]*w1,w2);
   }
   cout<<ans;
   //execute;
}

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