Submission #349831

#	Time	Username	Problem	Language	Result	Execution time	Memory
349831		Pety	Dreaming (IOI13_dreaming)	C++14	100 / 100	125 ms	29548 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"


using namespace std;

const int N = 1e5 + 2;
int up[N], k, down[N], bestTime[N], far;
bool viz[N];
vector<pair<int, int> > G[N];
void dfs (int nod, int p) {
  for (auto it : G[nod])
    if (it.first != p) {
      dfs(it.first, nod);
      down[nod] = max(down[nod], down[it.first] + it.second);
    }

}

void dfs2 (int nod, int p) {
  vector<int>pref;
  vector<int>suf;
  viz[nod] = 1;
  for (auto it : G[nod])
    if (it.first != p) {
      up[it.first] = up[nod] + it.second;
      pref.push_back(down[it.first] + it.second);
    }
  suf = pref;
  for (int i = 1; i < pref.size(); i++)
    pref[i] = max(pref[i - 1], pref[i]);
  for (int i = suf.size() - 2; i >= 0; i--)
    suf[i] = max(suf[i + 1], suf[i]);
  int useless = 0;
  for (auto it : G[nod])
    if (it.first != p) {
      int value = 0;
      if (useless > 0)
        value = pref[useless - 1];
      if (useless < suf.size() - 1)
        value = max(value, suf[useless + 1]);
      up[it.first] = max(up[it.first], value + it.second);
      useless++;
      dfs2(it.first, nod);
    }
  far = max(far,  max(down[nod],  up[nod]));
  bestTime[k] = min(bestTime[k], max(down[nod], up[nod]));
}

int travelTime (int n, int m, int l, int a[], int b[], int t[]) {
  for (int i = 0; i < m; i++) {
    a[i]++; b[i]++;
    G[a[i]].push_back({b[i], t[i]});
    G[b[i]].push_back({a[i], t[i]});
  }
  for (int i = 1; i <= n; i++)
    if (!viz[i]) {
      k++;
      bestTime[k] = 1e9 + 2;
      dfs(i, 0);
      dfs2(i, 0);
    }
  sort(bestTime + 1, bestTime + k + 1, greater<int>());
  if (k == 1)
    return max(far, bestTime[1]);
  if (k == 2)
    return max(far, l + bestTime[1] + bestTime[2]);
  else
    return max(far, max(l + bestTime[1] + bestTime[2], bestTime[2] + bestTime[3] + 2 * l));
}

int a[N], b[N], t[N], n, m, l;

/*int main ()
{
  cin >> n >> m >> l;
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> t[i];

  }
  cout << travelTime(n, m, l, a, b, t);
  return 0;
}*/
/**
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

**/

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int i = 1; i < pref.size(); i++)
      |                   ~~^~~~~~~~~~~~~
dreaming.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       if (useless < suf.size() - 1)
      |           ~~~~~~~~^~~~~~~~~~~~~~~~

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