Submission #322555

#	Time	Username	Problem	Language	Result	Execution time	Memory
322555		lukameladze	Dreaming (IOI13_dreaming)	C++14	65 / 100	665 ms	38496 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,anss;
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[]) 
{
	for (int i=0; i<=1e5; i++)
	v[i].clear();
	ans.clear();
     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])
          {
               vv.clear();
               ww=1;
               dfs(i,-1);
               x1=vert;
               ww=0;
               mx=0;
               dfs(x1,-1);
               x2=vert;
               dfs1(x2,-1);
               x=1e9;
               
               for (int j=0; j<vv.size(); j++)
               {
               	anss=max(anss, lv[vv[j]]);
               	anss=max(anss, lv1[vv[j]]);
                    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());

     if (ans.size()>=3)
     {
     	anss=max(anss,ans[1]+ans[2]+2*L);
     	anss=max(anss, ans[0]+ans[1]+L);
     	return anss;
         // cout<<anss<<endl;
     }
     if (ans.size()>=2)
     {
          anss=max(anss, ans[0]+ans[1]+L);
          return anss;
         // cout<<anss<<endl;
     }
     return 0;
}

Compilation message (stderr)

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

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