Submission #341473

#	Time	Username	Problem	Language	Result	Execution time	Memory
341473		A_D	Putovanje (COCI20_putovanje)	C++14	45 / 110	450 ms	37868 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;
int n;
void dfs2(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});
            dfs2(x,u,tar);
            if(bo)return ;
//            if(vec.empty())cout<<"46546465"<<endl;
            vec.pop_back();
        }
    }
    if(bo)return ;
}
void dfs(int u,int p)
{
    idx1[cnt]=u;
    idx[u]=cnt++;
    for(auto x:g[u]){
        if(x!=p)dfs(x,u);
    }
}
void qur()
{
    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++){
        dfs2(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;
}
main()
{
    int st;
    cin>>n;
    if(n<=2000){
        qur();
        return 0;
    }
    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: In function 'void qur()':
putovanje.cpp:70: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]
   70 |         for(int j=0;j<vec.size();j++){
      |                     ~^~~~~~~~~~~
putovanje.cpp: At global scope:
putovanje.cpp:84:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main()
      |      ^
putovanje.cpp: In function 'int main()':
putovanje.cpp:106:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |     dfs(st,st);
      |     ~~~^~~~~~~

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