Submission #720322

#	Time	Username	Problem	Language	Result	Execution time	Memory
720322		Yell0	Dreaming (IOI13_dreaming)	C++17	100 / 100	103 ms	19540 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<vector<pii>> gr;
vector<ll> std1,std2,mxd,rads;
vector<int> stdi,currt;
vector<bool> vis;
 
void dfs1(int u,int p) {
  currt.push_back(u);
  for(int i=0;i<gr[u].size();++i) {
    int v=gr[u][i].first,d=gr[u][i].second;
    if(v==p) continue;
    dfs1(v,u);
    if(std1[v]+d>std2[u]) std2[u]=std1[v]+d;
    if(std1[v]+d>=std1[u]) {
      std2[u]=std1[u];
      std1[u]=std1[v]+d;
      stdi[u]=i;
    }
  }
}
void dfs2(int u,int p,ll pd) {
  mxd[u]=max(std1[u],pd);
  for(int i=0;i<gr[u].size();++i) {
    int v=gr[u][i].first,d=gr[u][i].second;
    if(v==p) continue;
    if(stdi[u]==i) dfs2(v,u,max(pd,std2[u])+d);
    else dfs2(v,u,max(pd,std1[u])+d);
  }
}
 
int travelTime(int N,int M,int L,int A[],int B[],int T[]) {
  gr.resize(N);std1.resize(N,0);std2.resize(N,0);stdi.resize(N);vis.resize(N,0);mxd.resize(N,0);
  for(int i=0;i<M;++i) {
    gr[A[i]].push_back({B[i],T[i]});
    gr[B[i]].push_back({A[i],T[i]});
  }
  ll mxdia=0;
  for(int u=0;u<N;++u) {
    if(!vis[u]) {
      dfs1(u,-1);
      dfs2(u,-1,0);
      ll rad=LLONG_MAX;
      for(int v:currt) {
        vis[v]=1;
        rad=min(rad,mxd[v]);
        mxdia=max(mxdia,mxd[v]);
      }
      rads.push_back(rad);
      currt.clear();
    }
  }
  sort(rads.rbegin(),rads.rend());
  return max({mxdia,rads.size()>1?rads[0]+L+rads[1]:0,rads.size()>2?rads[1]+L+L+rads[2]:0});
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:14:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i=0;i<gr[u].size();++i) {
      |               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, ll)':
dreaming.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i=0;i<gr[u].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