Submission #726065

#	Time	Username	Problem	Language	Result	Execution time	Memory
726065		sofija6	Dreaming (IOI13_dreaming)	C++14	100 / 100	185 ms	17096 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define MAXN 100010
using namespace std;
vector<pair<int,int> > G[MAXN];
bool V[MAXN];
int maxx=0,cur,cnt[MAXN],ans=0;
vector<pair<int,int> > dist,v;
void DFS_Diameter(int i,int p,int d)
{
    V[i]=true;
    if (d>=maxx)
    {
        maxx=d;
        cur=i;
    }
    for (auto next : G[i])
    {
        if (next.first!=p)
            DFS_Diameter(next.first,i,d+next.second);
    }
}
void DFS_Distances(int i,int p,int d)
{
    dist.push_back({d,i});
    for (auto next : G[i])
    {
        if (next.first!=p)
            DFS_Distances(next.first,i,d+next.second);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (int i=0;i<M;i++)
    {
        G[A[i]].push_back({B[i],T[i]});
        G[B[i]].push_back({A[i],T[i]});
    }
    for (int i=0;i<N;i++)
    {
        if (!V[i])
        {
            int a=i,b=i;
            DFS_Diameter(i,i,0);
            a=cur;
            maxx=0;
            DFS_Diameter(a,a,0);
            b=cur;
            maxx=0;
            dist.clear();
            DFS_Distances(a,a,0);
            DFS_Distances(b,b,0);
            sort(dist.begin(),dist.end());
            for (auto x : dist)
            {
                cnt[x.second]++;
                if (cnt[x.second]==2)
                {
                    v.push_back(x);
                    break;
                }
            }
        }
    }
    sort(v.begin(),v.end());
    for (int i=0;i<v.size()-1;i++)
    {
        G[v[v.size()-1].second].push_back({v[i].second,L});
        G[v[i].second].push_back({v[v.size()-1].second,L});
    }
    DFS_Diameter(0,0,0);
    DFS_Diameter(cur,cur,0);
    return maxx;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0;i<v.size()-1;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