Submission #1188269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188269		prideliqueee	Dreaming (IOI13_dreaming)	C++20	100 / 100	51 ms	17480 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define f first
#define s second
int up[100010];
int down[100010];
int ans[100010];
int mx;
int mxx=0;
vector<pair<int,int>> ad[100010];
void dfs1(int u,int p)
{
    //down[u]=0;
    for(auto x:ad[u])
    {
        if(x.f!=p)
        {
            dfs1(x.f,u);
            down[u]=max(down[u],down[x.f]+x.s);
        }
    }
}
void dfs2(int u,int p)
{
    pair<int,int> mx1={-1,-1},mx2={-1,-1};
    for(auto x:ad[u])
    {
        if(x.f==p)
        continue;
        if(down[x.f]+x.s>=mx1.f)
        {
            mx2=mx1;
            mx1={down[x.f]+x.s,x.f};
        }
        else if(down[x.f]+x.s>mx2.f)
        {
            mx2={down[x.f]+x.s,x.f};
        }
    }
    for(auto x:ad[u])
    {
        if(x.f==p)
        continue;
        up[x.f]=max(up[x.f],up[u]+x.s);
        if(x.f==mx1.s)
        {
            if(mx2.s!=-1)
            up[x.f]=max(up[x.f],mx2.f+x.s);
        }
        else if(mx1.s!=-1)
        {
            up[x.f]=max(up[x.f],mx1.f+x.s);
        }
        dfs2(x.f,u);
    }
    ans[u]=max(down[u],up[u]);
    mx=min(mx,ans[u]);
    mxx=max(mxx,ans[u]);
    //cout<<mx<<" "<<ans[u]<<endl;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int n=N,m=M,l=L;
    int ans1,ans2,ans3;
    ans1=-1;
    ans2=-1;
    ans3=-1;
    for(int i=0;i<m;i++) 
    {
        ad[A[i]].emplace_back(B[i],T[i]);
        ad[B[i]].emplace_back(A[i],T[i]);
    }
    memset(ans,-1,sizeof ans);
    for(int i=0;i<n;i++)
    {
        if(ans[i]==-1)
        {
            mx=INT_MAX;
            dfs1(i,-1);
            dfs2(i,-1);
            if(mx>ans1)
            {
                
                ans3=ans2;
                ans2=ans1;
                ans1=mx;
            }
            else if(mx>ans2)
            {
                ans3=ans2;
                ans2=mx;
            }
            else if(mx>ans3)
            {
                ans3=mx;
            }
        }
    }
    int answer=max(ans1,mxx);
    if(ans2!=-1)
    answer=max(answer,ans1+ans2+l);
    if(ans3!=-1)
    answer=max(answer,ans2+ans3+l*2);
    return answer;
}

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