Submission #1183890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183890		I_FloPPed21	Dreaming (IOI13_dreaming)	C++20	100 / 100	48 ms	21832 KiB

dreaming

#include <iostream>
#include <algorithm>
#include <vector>
#include "dreaming.h"
using namespace std;
const int N=2e5+5;
int n,m;
long long l;
vector<pair<int,int>>adj[N];
long long ans=0;
long long sub[N],best[N][3],unde[N][2];
bool viz[N];
int A[N],B[N],T[N];
void dfs(int nod,int p)
{
    viz[nod]=true;
    for(auto [u,c]:adj[nod])
    {
        if(u!=p)
        {
            dfs(u,nod);
            if(best[nod][1]<sub[u]+c)
            {
                if(best[nod][1]>best[nod][2])
                {
                    best[nod][2]=best[nod][1];
                    unde[nod][2]=unde[nod][1];
                }
                best[nod][1]=sub[u]+c;
                unde[nod][1]=u;
            }
            else
                if(best[nod][2]<sub[u]+c)
            {
                best[nod][2]=sub[u]+c;
                unde[nod][2]=u;
            }
        }
    }
    sub[nod]=best[nod][1];
    ans=max(best[nod][1]+best[nod][2],ans);
}
long long rate=1e10;
void dfs2(int nod,int p,int cost)
{
    viz[nod]=true;
    if(p!=0)
    {
        if(unde[p][1]!=nod)
        {
            if(best[p][1]+cost>best[nod][1])
            {
                best[nod][2]=best[nod][1];
                unde[nod][2]=unde[nod][1];
                best[nod][1]=best[p][1]+cost;
                unde[nod][1]=p;
            }
            else
                if(best[p][1]+cost>best[nod][2])
            {
                best[nod][2]=best[p][1]+cost;
                unde[nod][2]=p;
            }
        }
        else
        if(unde[p][2]!=nod)
        {
            if(best[p][2]+cost>best[nod][1])
            {
                best[nod][2]=best[nod][1];
                unde[nod][2]=unde[nod][1];
                best[nod][1]=best[p][2]+cost;
                unde[nod][1]=p;
            }
            else
                if(best[p][2]+cost>best[nod][2])
                {
                    best[nod][2]=best[p][2]+cost;
                    unde[nod][2]=p;
                }
        }
    }
    rate=min(rate,max(best[nod][1],best[nod][2]));
    for(auto [u,c]:adj[nod])
    {
        if(u!=p)
        {
            dfs2(u,nod,c);
        }
    }
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    n=N,m=M,l=L;
    for(int i=0;i<m;i++)
    {
        int a=A[i],b=B[i];
        long long c=T[i];
        a++,b++;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==false)
        {
            dfs(i,0);
        }
    }
    for(int i=1;i<=n;i++)
        viz[i]=false;

    vector<long long>to_do;

    for(int i=1;i<=n;i++)
    {
        if(viz[i]==false)
        {
            dfs2(i,0,0);
            to_do.push_back(rate);
            rate=1e10;
        }
    }
    sort(to_do.begin(),to_do.end());
    if(to_do.size()==1)
        return ans;
    if(to_do.size()==2)
    {
        return max(ans,to_do[0]+to_do[1]+l);
    }
    long long a=to_do.back();
    to_do.pop_back();
    long long b=to_do.back();
    to_do.pop_back();
    long long c=to_do.back();
    ans=max(ans,a+b+l);
    ans=max(ans,b+c+2*l);
    return ans;
}
/*int main()
{
    cin>>n>>m>>l;
    for(int i=0;i<m;i++)
        cin>>A[i];
    for(int i=0;i<m;i++)
        cin>>B[i];
    for(int i=0;i<m;i++)
        cin>>T[i];

    cout<<travel_time(n,m,l,A,B,T);
    return 0;
}*/

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