Submission #1028613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028613		tolbi	Dreaming (IOI13_dreaming)	C++17	100 / 100	49 ms	9816 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int,int>>> arr(N);
    for (int i = 0; i < M; i++){
        arr[A[i]].push_back({B[i],T[i]});
        arr[B[i]].push_back({A[i],T[i]});
    }
    int ans = 0;
    vector<int> dp(N,-1);
    function<int(int)> f = [&](int src)->int{
        queue<array<int,3>> qu;
        qu.push({src,0,-1});
        int manode = src;
        int mm = 0;
        vector<int> gez;
        while (qu.size()){
            int node = qu.front()[0];
            int w = qu.front()[1];
            int lnode = qu.front()[2];
            qu.pop();
            if (w>mm) manode=node,mm=w;
            for (auto nex : arr[node]){
                if (nex.first==lnode) continue;
                qu.push({nex.first,nex.second+w,node});
            }
        }
        qu.push({manode,0,-1});
        while (qu.size()){
            int node = qu.front()[0];
            int w = qu.front()[1];
            int lnode = qu.front()[2];
            qu.pop();
            dp[node]=w;
            ans=max(ans,w);
            if (dp[node]>dp[manode]) manode=node;
            for (auto nex : arr[node]){
                if (nex.first==lnode) continue;
                qu.push({nex.first,nex.second+w,node});
            }
        }
        int ret = dp[manode];
        qu.push({manode,0,-1});
        while (qu.size()){
            int node = qu.front()[0];
            int w = qu.front()[1];
            int lnode = qu.front()[2];
            qu.pop();
            ret=min(ret,max(dp[node],w));
            for (auto &nex : arr[node]){
                if (nex.first==lnode) continue;
                qu.push({nex.first,nex.second+w,node});
            }
        }
        return ret;
    };
    vector<int> ansarr;
    for (int i = 0; i < N; ++i)
    {
        if (dp[i]==-1) {
            ansarr.push_back(f(i));
        }
    }
    if (ansarr.size()==1) return ans;
    sort(ansarr.begin(), ansarr.end());
    for (int i = 0; i < ansarr.size()-1; i++){
        ansarr[i]+=L;
    }
    sort(ansarr.begin(), ansarr.end());
    return max(ans,ansarr[ansarr.size()-1]+ansarr[ansarr.size()-2]);
}

Compilation message (stderr)

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