Submission #575410

#	Time	Username	Problem	Language	Result	Execution time	Memory
575410		ogibogi2004	Dreaming (IOI13_dreaming)	C++14	100 / 100	74 ms	22924 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
int sz=0;
bool vis[MAXN];
std::vector<std::pair<int,int> > g[MAXN];
int mpd[MAXN];// max path down
int biggest_current;
void dfs_init(int u,int par)
{
    mpd[u]=0;
    vis[u]=1;
    vector<int>f;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        dfs_init(xd.first,u);
        mpd[u]=max(xd.second+mpd[xd.first],mpd[u]);
        f.push_back(mpd[xd.first]+xd.second);
    }
    biggest_current=max(biggest_current,mpd[u]);
    sort(f.rbegin(),f.rend());
    if(f.size()>1)biggest_current=max(biggest_current,f[0]+f[1]);
}
int dfs_find(int u,int par,int len_up)
{
    int ret=max(mpd[u],len_up);
    int maxd=-1,ch=-1,che=-1;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        if(mpd[xd.first]>maxd)
        {
            maxd=mpd[xd.first];
            ch=xd.first;
            che=xd.second;
        }
    }
    if(ch==-1)
    {
        return ret;
    }
    len_up+=che;
    for(auto xd:g[u])
    {
        if(xd.first==par)continue;
        if(xd.first==ch)continue;
        len_up=max(len_up,mpd[xd.first]+che+xd.second);
    }
    return min(ret,dfs_find(ch,u,len_up));
}
void solve(int u)
{
    dfs_init(u,0);
    sz=dfs_find(u,0,0);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    for(int i=0;i<M;i++)
    {
        A[i]++;
        B[i]++;
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }
    vector<int>comps;
    for(int i=1;i<=N;i++)
    {
        if(vis[i]==0)
        {
            sz=0;
            solve(i);
            comps.push_back(sz);
        }
    }

    sort(comps.rbegin(),comps.rend());
    int ans=biggest_current;
    if(comps.size()==1)return max(ans,comps[0]);
    if(comps.size()==2)return max(ans,comps[0]+comps[1]+L);
    return max(ans,max(comps[0]+comps[1]+L,comps[1]+comps[2]+L+L));
}

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