Submission #586561

#	Time	Username	Problem	Language	Result	Execution time	Memory
586561		yutabi	Dreaming (IOI13_dreaming)	C++14	100 / 100	84 ms	16820 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

typedef pair <int,int> ii;



vector <vector <ii> > forest;
vector <bool> v;

int m;
int m_loc;

void DFS(int node, int curr=0, int par=-1)
{
    v[node]=1;

    if(curr>=m)
    {
        m=curr;

        m_loc=node;
    }

    for(int i=0;i<forest[node].size();i++)
    {
        if(forest[node][i].first!=par)
        {
            DFS(forest[node][i].first,curr+forest[node][i].second,node);
        }
    }

    return;
}

vector <int> P;

int DFS2(int node, int g, int par=-1)
{
    if(node==g)
    {
        int sum=0;

        for(int i=0;i<P.size();i++)
        {
            sum+=P[i];
        }

        int ans=sum;

        int sum2=0;

        for(int i=0;i<P.size();i++)
        {
            sum2+=P[i];

            ans=min(ans,max(sum-sum2,sum2));
        }

        P.clear();

        return ans;
    }

    for(int i=0;i<forest[node].size();i++)
    {
        if(forest[node][i].first!=par)
        {
            P.pb(forest[node][i].second);

            int res=DFS2(forest[node][i].first,g,node);

            if(res!=-1)
            {
                return res;
            }

            P.pop_back();
        }
    }

    return -1;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    v=vector <bool> (N,0);

    forest=vector <vector <ii> > (N);

    vector <int> ans;

    int a=0;

    for(int i=0;i<M;i++)
    {
        forest[A[i]].pb(ii(B[i],T[i]));
        forest[B[i]].pb(ii(A[i],T[i]));
    }

    for(int i=0;i<N;i++)
    {
        if(v[i]==0)
        {
            m=0;

            DFS(i);

            int p1=m_loc;

            m=0;

            DFS(p1);

            int p2=m_loc;

            a=max(a,m);

            ans.pb(DFS2(p1,p2));

            //printf("%d\n",ans.back());
        }
    }

    sort(ans.begin(),ans.end());

    if(ans.size()==1)
    {
        return max(a,ans[0]);
    }

    if(ans.size()==2)
    {
        return max(a,ans[0]+ans[1]+L);
    }

    return max(a,max(ans[ans.size()-1]+ans[ans.size()-2]+L,ans[ans.size()-2]+ans[ans.size()-3]+L+L));
}

Compilation message (stderr)

dreaming.cpp: In function 'void DFS(int, int, int)':
dreaming.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<forest[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int DFS2(int, int, int)':
dreaming.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=0;i<P.size();i++)
      |                     ~^~~~~~~~~
dreaming.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0;i<P.size();i++)
      |                     ~^~~~~~~~~
dreaming.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<forest[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~

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