Submission #822926

#	Time	Username	Problem	Language	Result	Execution time	Memory
822926		Warinchai	Dreaming (IOI13_dreaming)	C++14	100 / 100	83 ms	19152 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int p[100005];
int mxp[100005];
int mxl[100005];
pair<int,int>mxc[100005];
vector<pair<int,int> >v[100005];
int fp(int a){
    if(p[a]==a){
        return a;
    }
    return p[a]=fp(p[a]);
}
void un(int a,int b){
    p[fp(a)]=fp(b);
}
int mxx=0;
int fmxl(int x,int p){
    if(p==-1&&v[x].size()==0){
        return 0;
    }
    if(v[x].size()==1&&p!=-1){
        return 0;
    }
    int se=0,fi=0;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].first==p){
            continue;
        }
        int val=fmxl(v[x][i].first,x)+v[x][i].second;
        if(val>fi){
            se=fi;
            fi=val;
        }else{
            se=max(se,val);
        }
    }
    //cout<<x<<" "<<fi<<" "<<se<<endl;
    mxc[x]={fi,se};
    if(fi+se>mxx){
        mxx=fi+se;
    }
    return fi;
}
int ans=INT_MAX;
void fmxp(int x,int p,int mp){
    int val=max(mp,mxc[x].first);
    //cout<<x<<" "<<mp<<" "<<mxc[x].first<<" "<<val<<endl;
    ans=min(ans,val);
    //cout<<"ans:"<<ans<<endl;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i].first==p){
            continue;
        }
        //cout<<"before "<<v[x][i].first<<":"<<mp+;
        int nmp=max(mp,(mxc[v[x][i].first].first+v[x][i].second==mxc[x].first?mxc[x].second:mxc[x].first))+v[x][i].second;
        fmxp(v[x][i].first,x,nmp);
    }
}
vector<int>prr;
vector<int>cpmx;
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i=0;i<n;i++){
        p[i]=i;
    }
    for(int i=0;i<m;i++){
        un(a[i],b[i]);
        v[a[i]].push_back({b[i],t[i]});
        v[b[i]].push_back({a[i],t[i]});
    }
    for(int i=0;i<n;i++){
        if(p[i]==i){
            prr.push_back(i);
        }
    }
    int tmmx=0;
    for(int i=0;i<prr.size();i++){
        //cout<<prr[i]<<":"<<endl;
        mxx=0;
        //cout<<"fmxl:"<<prr[i]<<endl;
        fmxl(prr[i],-1);
        mxl[prr[i]]=mxx;
        if(mxx>tmmx){
            tmmx=mxx;
        }
        //cout<<"fmxp:"<<prr[i]<<endl;
        ans=INT_MAX;
        fmxp(prr[i],-1,0);
        mxp[prr[i]]=ans;
        cpmx.push_back(ans);
        //cout<<mxx<<" "<<ans<<endl;
    }
    sort(cpmx.begin(),cpmx.end(),greater<int>());
    int rans=0;
    if(n-m>=2){
        rans=max(rans,cpmx[0]+cpmx[1]+l);
    }
    if(n-m>=3){
        rans=max(rans,cpmx[1]+cpmx[2]+l*2);
    }
    rans=max(rans,tmmx);
    return rans;
}

/*
int ar1[100005];
int ar2[100005];
int t1[100005];
int main(){
    int n,m,l;
    cin>>n>>m>>l;
    for(int i=0;i<m;i++){
        cin>>ar1[i]>>ar2[i]>>t1[i];
    }
    cout<<travelTime(n,m,l,ar1,ar2,t1);
}*/

Compilation message (stderr)

dreaming.cpp: In function 'int fmxl(int, int)':
dreaming.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'void fmxp(int, int, int)':
dreaming.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<prr.size();i++){
      |                 ~^~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23