제출 #715099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715099		hackerbhaiya	Putovanje (COCI20_putovanje)	C++14	110 / 110	221 ms	38528 KiB

putovanje

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

ll n;
vector<vector<array<ll,2> > > v;
vector<array<ll,3> > ed;
vector<vector<ll> > dp;
vector<ll> dis,tot;

void dfs(ll cur, ll par)
{
    dp[cur][0]=par;
    f(i,0,sz(v[cur]))
    {
        ll node=v[cur][i][0],e=v[cur][i][1];
        if(node!=par)
        {
            dis[node]=1+dis[cur];
            dfs(node,cur);
            ed[e][0]=tot[node],tot[cur]+=tot[node];
        }
    }
}

const int N=21;
int kth_ancestor(int node, int k)
{
    f(i,0,N)
    {
        if(k&1)
            node=dp[node][i];
        k>>=1;
    }
    return node;
}
 
int find(int a, int b)
{
    if(dis[a]<dis[b])
        swap(a,b);
    int dif=dis[a]-dis[b];
    a=kth_ancestor(a,dif);
    if(a==b)
        return a;
    rf(i,N-1,0)
    {
        if(dp[a][i]!=dp[b][i])
            a=dp[a][i],b=dp[b][i];
    }
    return dp[a][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(ilu,1,z+1)
    {
        // cout<<"Case #"<<ilu<<": ";
        cin>>n;
        v.rz(n+1),ed.rz(n-1),dp.rz(n+1,vector<ll> (N,-1)),dis.rz(n+1),tot.rz(n+1);
        f(i,0,n-1)
        {
            ll l,r,x,y;
            cin>>l>>r>>x>>y;
            ed[i]={0,x,y};
            v[l].pb({r,i}),v[r].pb({l,i});
        }
        dfs(1,1);
        f(j,1,N)
        {
            f(i,1,n+1)
                dp[i][j]=dp[dp[i][j-1]][j-1];
        }

        f(i,1,n)
        {
            ll l=i,r=i+1,lc=find(l,r);
            tot[l]++,tot[r]++,tot[lc]-=2;
        }
        dfs(1,1);

        ll ans=0;
        f(i,0,n-1)
            ans+=min(ed[i][0]*ed[i][1],ed[i][2]);
        cout<<ans;
    }
}

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