Submission #341471

#	Time	Username	Problem	Language	Result	Execution time	Memory
341471		A_D	Putovanje (COCI20_putovanje)	C++14	25 / 110	363 ms	39660 KiB

putovanje

/*
ID: antwand1
TASK: pprime
LANG: C++
*/
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define du long double
#define F first
#define S second
#define FOR(a,b) for(int a=1;a<=b;a++)
#define FORl(a,b) for(a=1;a<=b;a++)
#define FOR0(a,b) for(int a=1;a<b;a++)
#define FORl0(a,b) for(a=0;a<b;a++)
#define ii pair<int,int>
using namespace std;
const int N=2e5+1;
map<ii,ii> mp;
vector<int> g[N];
map<ii,int> freq;
vector<ii> vec;
bool bo=0;
int idx[N];
int idx1[N];
int pre[N];
int cnt=1;
void dfs(int u,int p)
{
    idx1[cnt]=u;
    idx[u]=cnt++;
    for(auto x:g[u]){
        if(x!=p)dfs(x,u);
    }
}
main()
{
    int n,st;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        g[a].push_back(b);
        g[b].push_back(a);
        mp[{a,b}]={c,d};
        mp[{b,a}]={c,d};
    }
    for(int i=1;i<=n;i++){
        if(g[i].size()==1){
            st=i;
            break;
        }
    }
    dfs(st,st);
    for(int i=1;i<n;i++){
        st=idx[i];
        int en=idx[i+1];
        if(st>en)swap(st,en);
        pre[st]++;
        pre[en]--;
    }
    for(int i=1;i<=n;i++)pre[i]+=pre[i-1];
    for(int i=1;i<n;i++){
        int mn=idx1[i];
        int mx=idx1[i+1];
//        cout<<pre[i]<<" "<<mn<<endl;
        if(mn>mx)swap(mn,mx);
        freq[{mn,mx}]=pre[i];
    }
    int ans=0;
    for(auto x:freq){
  //      cout<<x.F.F<<" "<<x.F.S<<" "<<x.S<<endl;
        ans+=min(mp[{x.F.F,x.F.S}].S,x.S*mp[{x.F.F,x.F.S}].F);
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

putovanje.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main()
      |      ^
putovanje.cpp: In function 'int main()':
putovanje.cpp:54:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     dfs(st,st);
      |     ~~~^~~~~~~

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