Submission #341414

#TimeUsernameProblemLanguageResultExecution timeMemory
341414A_DPutovanje (COCI20_putovanje)C++14
20 / 110
1104 ms38652 KiB
/*
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;
void dfs(int u,int p,int tar)
{
    if(bo)return ;
    if(u==tar){
        bo=1;
        return;
    }
  //  cout<<u<<endl;
    for(auto x:g[u]){
        if(bo)return ;
        if(x!=p){
            vec.push_back({u,x});
            dfs(x,u,tar);
            if(bo)return ;
//            if(vec.empty())cout<<"46546465"<<endl;
            vec.pop_back();
        }
    }
    if(bo)return ;
}
main()
{
    int n;
    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++){
        dfs(i,i,i+1);
  //      cout<<vec.size()<<endl;
        for(int j=0;j<vec.size();j++){
            if(vec[j].F>vec[j].S)swap(vec[j].F,vec[j].S);
            freq[{vec[j].F,vec[j].S}]++;
        }
        vec.clear();
        bo=0;
    }
    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:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main()
      |      ^
putovanje.cpp: In function 'int main()':
putovanje.cpp:59:22: 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]
   59 |         for(int j=0;j<vec.size();j++){
      |                     ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...