Submission #583321

#	Time	Username	Problem	Language	Result	Execution time	Memory
583321		AGE	Putovanje (COCI20_putovanje)	C++14	110 / 110	513 ms	87616 KiB

putovanje

#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long

using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;
int n,up[N][30],innode[N],outnode[N],timee=0,val[N],val2[N];
map<pair<int,int>,int>mpp;
vector<int>adj[N];
vector<pair<int,int>>v;

void dfs(int node,int par){

    innode[node]=timee++;
    up[node][0]=par;
    for(int j=1;j<ceil(log2(n));j++)
        up[node][j]=up[up[node][j-1]][j-1];

    for(auto x:adj[node]){

        if(x==par)
            continue;

        dfs(x,node);

    }

    outnode[node]=timee++;

}

bool is_parent(int x,int y){
    return innode[x]<=innode[y]&&outnode[x]>=outnode[y];
}

int lca(int x,int y){

    if(is_parent(x,y))
        return x;

    if(is_parent(y,x))
        return y;


    for(int i=ceil(log2(n))+1;i>=0;i--){

        if(!is_parent(up[x][i],y))
            x=up[x][i];
    }

    return up[x][0];

}

void dfs2(int node,int par){

    for(auto x:adj[node]){

        if(x==par)
            continue;

        dfs2(x,node);

        val2[node]+=val2[x];
        mpp[{node,x}]=val2[x];
        mpp[{x,node}]=val2[x];

    }

    val2[node]+=val[node];
}
main()
{

    cin>>n;

    map<pair<int,int>,pair<int,int>>mp;

    for(int i=0;i<n-1;i++){

        int x,y,cost1,cost2;
        cin>>x>>y>>cost1>>cost2;

        v.pb({x,y});
        mp[{x,y}]={cost1,cost2};
        adj[x].pb(y);
        adj[y].pb(x);
    }

    dfs(1,0);
    innode[0]=-1;
    outnode[0]=++timee;

    for(int i=2;i<=n;i++){

        int lcaa=lca(i,i-1);
        val[i]++;
        val[i-1]++;
        val[lcaa]-=2;

    }


    dfs2(1,0);

    int ans=0;



    for(int i=0;i<v.size();i++){

        int cost1=mp[{v[i].F,v[i].S}].F*mpp[{v[i].F,v[i].S}];
        int cost2=mp[{v[i].F,v[i].S}].S;
        ans+=min(cost1,cost2);

    }

    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

putovanje.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main()
      | ^~~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:112:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

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