Submission #322510

#	Time	Username	Problem	Language	Result	Execution time	Memory
322510		lukameladze	Dreaming (IOI13_dreaming)	C++14	18 / 100	385 ms	34436 KiB

dreaming

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
long long ww,lv[300005],lv1[300005],mx,vert,fix[300005],x1,x2,x,y;
std::vector <long long> v[300005],vv,ans;
map < pair <long long, long long > , long long > mp; 
void dfs(int a, int p)
{
    fix[a]=1;
     if (ww==1) vv.push_back(a);
     if (p!=-1)
     lv[a]=lv[p]+mp[{a,p}];
     else lv[a]=0;
     if (lv[a]>mx)
     {
          vert=a;
          mx=lv[a];
     }
     for (int i=0; i<v[a].size(); i++) 
     {
          if (v[a][i]!=p)
          {
               dfs(v[a][i],a);
          }
     }
}
void dfs1(int a, int p)
{
     if (p!=-1)
     lv1[a]=lv1[p]+mp[{a,p}];
     else lv1[a]=0;
     for (int i=0; i<v[a].size(); i++)
     {
          if (v[a][i]!=p)
          {
               dfs1(v[a][i],a);
          }
     }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    /*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];
    }*/
     for (int i=0; i<M; i++)
     {
          mp[{A[i],B[i]}]=T[i];
          mp[{B[i],A[i]}]=T[i];
          v[A[i]].push_back(B[i]);
          v[B[i]].push_back(A[i]);
     }

     for (int i=0; i<N; i++)
     {
            mx=0;
          if (!fix[i])
          {
              //cout<<i<<"   s"<<endl;
               vv.clear();
             //  cout<<i<<endl<<endl;
               ww=1;
               dfs(i,-1);
               x1=vert;
             //  cout<<lv[9]<<" "<<lv[3]<<" "<<lv[5]<<" "<<lv[11]<<endl;
               ww=0;
               mx=0;
               dfs(x1,-1);
              // cout<<x1<<"   h "<<lv[0]<<endl;
               
               x2=vert;
               dfs1(x2,-1);
               //cout<<lv[8]<<"    "<<lv1[8]<<endl;
               x=1e9;
              // cout<<x1<<"    s    "<<x2<<endl;
               for (int j=0; j<vv.size(); j++)
               {
                //   cout<<vv[j]<<" "<<lv[vv[j]]<<"   "<<lv1[vv[j]]<<endl;
                    y=max(lv[vv[j]], lv1[vv[j]]);
                    x=min(x, y);
               }
               ans.push_back(x);
               //cout<<x<<endl;
          }
     }
     sort(ans.begin(), ans.end());
     reverse(ans.begin(), ans.end());
    // cout<<endl;
     if (ans.size()>=3)
     {
          return max(ans[1]+ans[2]+2*L, ans[0]+ans[1]+L);
     }
     if (ans.size()>=2)
     {
          return ans[0]+ans[1]+L;
     }
     return 0;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:21:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |      for (int i=0; i<v[a].size(); i++)
      |                    ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |      for (int i=0; i<v[a].size(); i++)
      |                    ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |                for (int j=0; j<vv.size(); j++)
      |                              ~^~~~~~~~~~

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