Submission #731415

#	Time	Username	Problem	Language	Result	Execution time	Memory
731415		lucri	Dreaming (IOI13_dreaming)	C++17	100 / 100	106 ms	12524 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
int nr,t[100010],v[100010],pd[100010],n,m,l,ans;
bool viz[100010];
std::vector<std::vector<std::pair<int,int>>>a;
inline int tata(int nod)
{
    if(t[nod]==nod)
        return nod;
    return t[nod]=tata(t[nod]);
}
inline void parcurge1(int nod,int &nod2,int &vnod2)
{
    viz[nod]=true;
    if(pd[nod]>vnod2)
    {
        vnod2=pd[nod];
        nod2=nod;
    }
    for(auto x:a[nod])
    {
        if(viz[x.first]==false)
        {
            pd[x.first]=pd[nod]+x.second;
            parcurge1(x.first,nod2,vnod2);
            pd[x.first]=0;
        }
    }
}
inline void parcurge2(int nod,int &vnod)
{
    viz[nod]=false;
    if(pd[nod]>vnod)
        vnod=pd[nod];
    for(auto x:a[nod])
    {
        if(viz[x.first]==true)
        {
            pd[x.first]=pd[nod]+x.second;
            parcurge2(x.first,vnod);
            pd[x.first]=0;
        }
    }
}
inline int diametru(int nod)
{
    int nod2=nod,vnod2=0;
    parcurge1(nod,nod2,vnod2);
    vnod2=0;
    parcurge2(nod2,vnod2);
    return vnod2;
}
inline void initpd(int nod)
{
    viz[nod]=true;
    for(auto x:a[nod])
    {
        if(viz[x.first]==false)
        {
            initpd(x.first);
            pd[nod]=std::max(pd[nod],pd[x.first]+x.second);
        }
    }
}
inline int greutate(int nod)
{
    int ans=1000000000,rad=nod,rado=nod;
    do
    {
        int ansa=0;
        nod=rad;
        for(auto x:a[nod])
        {
            if(x.second+pd[x.first]>ansa)
            {
                ansa=x.second+pd[x.first];
                rad=x.first;
            }
        }
        if(ansa<ans)
        {
            ans=ansa;
            rado=nod;
        }
        pd[nod]=0;
        for(auto x:a[nod])
        {
            if(x.first!=rad)
            {
                if(x.second+pd[x.first]>pd[nod])
                    pd[nod]=x.second+pd[x.first];
            }
        }
    }while(rado!=rad);
    return ans;
}
inline int construieste(int nod)
{
    int dim=diametru(nod);
    ans=std::max(ans,dim);
    if(dim==0)
        return 0;
    initpd(nod);
    return greutate(nod);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n=N;
    m=M;
    l=L;
    a.resize(n+5);
    ans=0;
    for(int i=0;i<n;++i)
        t[i]=i;
    for(int i=0;i<m;++i)
    {
        a[A[i]].push_back({B[i],T[i]});
        a[B[i]].push_back({A[i],T[i]});
        t[t[A[i]]]=tata(B[i]);
    }
    for(int i=0;i<n;++i)
        if(viz[i]==false)
            v[++nr]=construieste(i);
    std::sort(v+1,v+nr+1);
    if(nr>=2)
        ans=std::max(ans,L+v[nr]+v[nr-1]);
    if(nr>=3)
        ans=std::max(ans,2*L+v[nr-2]+v[nr-1]);
    return ans;
}

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