Submission #522799

#	Time	Username	Problem	Language	Result	Execution time	Memory
522799		Deepesson	Dreaming (IOI13_dreaming)	C++17	100 / 100	519 ms	15680 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define MAX 105000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
bool foi[MAX];
int visitou[MAX]={};
int turno=42;
int mais_distante(int x){
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    queue.push({0,x});
    int last=0;
    ++turno;
    while(queue.size()){
        auto __ = queue.top();
        queue.pop();
        if(visitou[__.second]==turno)continue;
        visitou[__.second]=turno;
        last=__.second;
        for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
    }
    return last;
}
int maior_distancia(int x){
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    queue.push({0,x});
    int last=0;
    ++turno;
    while(queue.size()){
        auto __ = queue.top();
        queue.pop();
        if(visitou[__.second]==turno)continue;
        visitou[__.second]=turno;
        last=__.first;
        for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
    }
    return last;
}
std::vector<int> marcar(int x){
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
    queue.push({0,x});
    std::vector<int> v;
    ++turno;
    while(queue.size()){
        auto __ = queue.top();
        queue.pop();
        if(visitou[__.second]==turno)continue;
        visitou[__.second]=turno;
        v.push_back(__.second);
        foi[__.second]=true;
        for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
    }
    return v;
}
int maiordist[MAX]={};
int meio(int x){
    int ponta1 = mais_distante(mais_distante(x));
    int ponta2 = mais_distante(ponta1);
    std::vector<int> checar;
    {
        std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
        queue.push({0,ponta1});
        ++turno;
        while(queue.size()){
            auto __ = queue.top();
            queue.pop();
            if(visitou[__.second]==turno)continue;
            visitou[__.second]=turno;
            checar.push_back(__.second);
            maiordist[__.second]=__.first;
            for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
        }
    }
    {
        std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;
        queue.push({0,ponta2});
        ++turno;
        while(queue.size()){
            auto __ = queue.top();
            queue.pop();
            if(visitou[__.second]==turno)continue;
            visitou[__.second]=turno;
            maiordist[__.second]=std::max(maiordist[__.second],__.first);
            for(auto&x:con[__.second])queue.push({__.first+x.second,x.first});
        }
    }
    int best=-1;
    int val=1e9+7;
    for(auto&x:checar){
        if(maiordist[x]<val){
            val=maiordist[x];
            best=x;
        }
    }
    return best;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i!=M;++i){
        con[A[i]].push_back({B[i],T[i]});
        con[B[i]].push_back({A[i],T[i]});
    }
    std::vector<std::vector<int>> vec;
    for(int i=0;i!=N;++i){
        if(foi[i])continue;
        vec.push_back(marcar(i));
    }
    std::vector<pii> meios;
    for(auto&x:vec){
        int k = meio(x[0]);
        meios.push_back({maior_distancia(k),meio(x[0])});
    }
    std::sort(meios.begin(),meios.end(),std::greater<pii>());
    for(int i=1;i<meios.size();++i){
        con[meios[i].second].push_back({meios[0].second,L});
        con[meios[0].second].push_back({meios[i].second,L});
    }
    return maior_distancia(mais_distante(mais_distante(0)));
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:113: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]
  113 |     for(int i=1;i<meios.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