Submission #169265

#	Time	Username	Problem	Language	Result	Execution time	Memory
169265		AlexLuchianov	Dreaming (IOI13_dreaming)	C++14	100 / 100	108 ms	24952 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <iostream>

int const nmax = 100000;
int const inf = 1000000000;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

struct Edge{
  int to;
  int cost;
};
std::vector<Edge> g[1 + nmax];
int seen[1 + nmax], dp[1 + nmax];

void dfs(int node, int parent){
  seen[node] = 1;
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    if(parent == e.to)
      g[node].erase(g[node].begin() + h);
  }
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    dfs(e.to, node);
    dp[node] = MAX(dp[node], dp[e.to] + e.cost);
  }
}

int dfs2(int node, int parent, int acc, int &resultall){
  int result = MAX(acc, dp[node]);
  resultall = MAX(resultall, MAX(acc, dp[node]));

  std::vector<int> pref(g[node].size()), suff(g[node].size());
  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    pref[h] = suff[h] = dp[e.to] + e.cost;
  }

  for(int h = 0; h < g[node].size(); h++)
    if(0 < h)
      pref[h] = MAX(pref[h], pref[h - 1]);
  for(int h = g[node].size() - 1; 0 <= h; h--)
    if(h + 1 < g[node].size())
      suff[h] = MAX(suff[h], suff[h + 1]);

  for(int h = 0; h < g[node].size(); h++){
    Edge e = g[node][h];
    int newacc = acc;
    if(0 < h)
      newacc = MAX(newacc, pref[h - 1]);
    if(h + 1 < g[node].size())
      newacc = MAX(newacc, suff[h + 1]);

    int result2 = dfs2(e.to, node, e.cost + newacc, resultall);
    result = MIN(result, result2);
  }
  return result;
}

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]});
  }
  std::vector<int> sol;
  int resultall = 0;
  for(int i = 0; i < N; i++)
    if(seen[i] == 0){
      dfs(i, -1);
      sol.push_back(dfs2(i, -1, 0, resultall));
    }
  sort(sol.begin(), sol.end());

  if(sol.size() == 1)
    return MAX(resultall, sol[0]);
  else if(sol.size() == 2)
    return MAX(resultall, sol[0] + sol[1] + L);
  else
    return MAX(resultall, MAX(sol[sol.size() - 1] + sol[sol.size() - 2] + L, sol[sol.size() - 2] + sol[sol.size() - 3] + L * 2));
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
dreaming.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs2(int, int, int, int&)':
dreaming.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
dreaming.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++)
                  ~~^~~~~~~~~~~~~~~~
dreaming.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(h + 1 < g[node].size())
        ~~~~~~^~~~~~~~~~~~~~~~
dreaming.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~
dreaming.cpp:56:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(h + 1 < g[node].size())
        ~~~~~~^~~~~~~~~~~~~~~~

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