Submission #1148831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148831		AlgorithmWarrior	Dreaming (IOI13_dreaming)	C++20	100 / 100	46 ms	17220 KiB

dreaming

#include <bits/stdc++.h>
#define MAX 100005
#include "dreaming.h"

using namespace std;

struct str
{
    int dist;
    int where;
}Longest[MAX];
int LongestRev[MAX];
struct str2
{
    int node;
    int len;
};
vector<str2>tree[MAX];
int n,m,l;
bool visited[MAX];
int parent[MAX];
int dpar[MAX];
int root[MAX];
int diam[MAX];

void find_longest(int node,int rt)
{
    root[node]=rt;
    visited[node]=1;
    for(auto structure : tree[node])
    {
        int son=structure.node;
        int len=structure.len;
        if(!visited[son])
        {
            parent[son]=node;
            dpar[son]=len;
            find_longest(son,rt);
            if(Longest[node].dist<Longest[son].dist+len)
            {
                Longest[node].dist=Longest[son].dist+len;
                Longest[node].where=son;
            }
        }
    }
    if(!Longest[node].dist)
        Longest[node].where=node;
}

void debug_longest()
{
    int i;
    for(i=1;i<=n;++i)
        cout<<Longest[i].dist<<' '<<Longest[i].where<<'\n';
}

void init_Longest()
{
    int i;
    for(i=1;i<=n;++i)
        if(!visited[i])
            find_longest(i,i);
    for(i=1;i<=n;++i)
        visited[i]=0;
}

void find_longest_rev(int node)
{
    visited[node]=1;
    LongestRev[node]=max(LongestRev[node],LongestRev[parent[node]]+dpar[node]);
    int max1=0,max2=0;
    for(auto structure : tree[node])
    {
        int son=structure.node;
        int len=structure.len;
        if(son!=parent[node])
        {
            if(max1<Longest[son].dist+len)
            {
                max2=max1;
                max1=Longest[son].dist+len;
            }
            else
                if(max2<Longest[son].dist+len)
                    max2=Longest[son].dist+len;
        }
    }
    for(auto structure : tree[node])
    {
        int son=structure.node;
        int len=structure.len;
        if(son!=parent[node])
        {
            if(Longest[son].dist+len==max1)
                LongestRev[son]=max2+len;
            else
                LongestRev[son]=max1+len;
            find_longest_rev(son);
        }
    }
}

void init_Longest_rev()
{
    int i;
    for(i=1;i<=n;++i)
        if(!visited[i])
            find_longest_rev(i);
    for(i=1;i<=n;++i)
        visited[i]=0;
}

void debug_longest_rev()
{
    int i;
    for(i=1;i<=n;++i)
        cout<<LongestRev[i]<<' ';
}

void find_optimal(int node,int& answer)
{
    if(visited[node])
        return;
    visited[node]=1;
    answer=min(answer,max(Longest[node].dist,LongestRev[node]));
    if(Longest[node].dist>LongestRev[node])
        find_optimal(Longest[node].where,answer);
    else
        find_optimal(parent[node],answer);
}

void diameter()
{
    int i;
    for(i=1;i<=n;++i)
    {
        int rt=root[i];
        diam[rt]=max(diam[rt],max(Longest[i].dist,LongestRev[i]));
    }
}

int init_opt()
{
    int max1=-1e9,max2=-1e9,max3=-1e9;
    int maxim=0;
    int i;
    for(i=1;i<=n;++i)
        if(!visited[root[i]])
        {
            maxim=max(maxim,diam[root[i]]);
            int answer=2e9;
            find_optimal(i,answer);
            if(answer>max1)
            {
                max3=max2;
                max2=max1;
                max1=answer;
            }
            else
                if(answer>max2)
                {
                    max3=max2;
                    max2=answer;
                }
                else
                    if(answer>max3)
                        max3=answer;
        }
    return max(maxim,max(max1+max2+l,max2+max3+2*l));
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    n=N;
    m=M;
    l=L;
    int i;
    for(i=0;i<m;++i)
    {
        int node1,node2,len;
        node1=A[i];
        node2=B[i];
        len=T[i];
        ++node1;
        ++node2;
        tree[node1].push_back({node2,len});
        tree[node2].push_back({node1,len});
    }
    init_Longest();
    init_Longest_rev();
    diameter();
    return init_opt();
}

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