Submission #543888

#	Time	Username	Problem	Language	Result	Execution time	Memory
543888		krit3379	Dreaming (IOI13_dreaming)	C++17	100 / 100	80 ms	21324 KiB

dreaming

#include<bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define N 100005

int dep[N],ans;
vector<int> val;
vector<pair<int,int>> g[N];
pair<int,int> ma1[N],ma2[N];
bitset<N> vis;

int dfs(int s,int f){
    vis[s]=true;
    for(auto x:g[s]){
        if(x.first==f)continue;
        int d=dfs(x.first,s)+x.second;
        pair<int,int> pa=make_pair(d,x.first);
        if(pa>ma1[s])swap(pa,ma1[s]);
        if(pa>ma2[s])swap(pa,ma2[s]);
        dep[s]=max(dep[s],d);
    }
    ans=max(ans,ma1[s].first+ma2[s].first);
    return dep[s];
}

int cal(int s,int f,int carry){
    vis[s]=true;
    int m;
    m=max(carry,ma1[s].first);
    for(auto x:g[s]){
        if(x.first==f)continue;
        if(ma1[s].second==x.first)m=min(m,cal(x.first,s,max(carry,ma2[s].first)+x.second));
        else m=min(m,cal(x.first,s,max(carry,ma1[s].first)+x.second));
    }
    return m;
}

int travelTime(int n, int m, int l, int u[N], int v[N], int t[N]){
    int i,a,b,w,com;
    for(i=0;i<m;i++){
        a=u[i],b=v[i],w=t[i];
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    com=n-m;
    for(i=0;i<n;i++)ma1[i]=ma2[i]={0,-1};
    for(i=0;i<n;i++)if(!vis[i])dfs(i,-1);
    vis=0;
    for(i=0;i<n;i++)if(!vis[i])val.push_back(cal(i,-1,0));
    sort(val.begin(),val.end(),greater<int>());
    if(val.size()>1)ans=max(ans,val[0]+val[1]+l);
    if(val.size()>2)ans=max(ans,val[1]+val[2]+2*l);
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:39:17: warning: variable 'com' set but not used [-Wunused-but-set-variable]
   39 |     int i,a,b,w,com;
      |                 ^~~

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