Submission #371011

#	Time	Username	Problem	Language	Result	Execution time	Memory
371011		Fysty	Dreaming (IOI13_dreaming)	C++17	100 / 100	137 ms	20960 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
const ll INF=2e18;
vector<pll> ed[100005];
ll dist[100005],n,m,maxx=0,vis[100005];
vector<ll> tmp,path;
void dfs(ll u,ll p)
{
    tmp.pb(u);
    for(auto v:ed[u])
    {
        if(v.F==p) continue;
        dist[v.F]=dist[u]+v.S;
        dfs(v.F,u);
    }
}
bool findpath(ll u,ll p,ll d)
{
    bool ret=0;
    if(dist[u]==d) ret=1;
    for(auto v:ed[u])
    {
        if(v.F==p) continue;
        if(findpath(v.F,u,d)) ret=1;
    }
    if(ret) path.pb(dist[u]);
    return ret;
}
ll findmid(ll st)
{
    tmp.clear();
    path.clear();
    dfs(st,-1);
    ll mx=-1,s=-1;
    for(ll u:tmp)
    {
        if(mx<dist[u]) mx=dist[u],s=u;
        dist[u]=0,vis[u]=1;
    }
    tmp.clear();
    dfs(s,-1);
    mx=-1;
    ll t=-1;
    for(ll u:tmp) if(mx<dist[u]) mx=dist[u],t=u;
    maxx=max(maxx,mx);
    findpath(s,-1,mx);
    ll mn=INF;
    for(ll u:path) mn=min(mn,max(mx-u,u));
    //cout<<st<<" "<<mn<<"\n";
    return mn;
}
int travelTime(int N,int M,int L,int A[], int B[], int T[])
{
    n=N,m=M;
    ll l=L;
    vector<ll> ans;
    rep(i,m)
    {
        ll u=A[i],v=B[i],w=T[i];
        ed[u].pb({v,w});
        ed[v].pb({u,w});
    }
    rep(i,n)
    {
        if(vis[i]) continue;
        ans.pb(findmid(i));
    }
    sort(ans.begin(),ans.end(),greater<ll>());
    if(ans.size()==1) return maxx;
    else if(ans.size()==2) return max(maxx,ans[0]+ans[1]+l);
    else return max({maxx,ans[0]+ans[1]+l,ans[1]+ans[2]+2*l});
}

Compilation message (stderr)

dreaming.cpp: In function 'll findmid(ll)':
dreaming.cpp:51:8: warning: variable 't' set but not used [-Wunused-but-set-variable]
   51 |     ll t=-1;
      |        ^

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