Submission #492034

#	Time	Username	Problem	Language	Result	Execution time	Memory
492034		lorenzoferrari	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KiB

dreaming

// a) ans = max(diametri)
// b) max "code", dove coda = min(max distanza da un nodo)
//  if 1 componente: return ans
//  ans = max(ans, codaMax[0] + codaMax[1] + L)
//  if 2 componenti: return ans
//  ans = max(ans, codaMax[1] + codaMax[2] + 2*L)
//  return ans

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> c;
vector<vector<pair<int, int>>> g;
vector<int> cmp;
int gty = 0;
array<int, 2> dmax;
vector<int> d, p, vis;

void dfs1(int v) {
  cmp[v] = gty;
  c.back().push_back(v);
  for (auto [u, w] : g[v])
    if (cmp[u] != gty)
      dfs1(u);
}

void dfs(int v, int ty) {
  vis[v] = ty;
  if (d[v] > dmax[1])
    dmax = {v, d[v]};
  for (auto [u, w] : g[v]) {
    if (vis[u] != ty) {
      d[u] = d[v] + w;
      dfs(u, ty);
    }
  }
}

int diam(int v) {
  dmax = {v, 0}; dfs(v, gty++);
  v = dmax[0]; d[v] = 0;
  dfs(v, gty++);
  return dmax[1];
}

int coda(int v) {
  // cout << "coda[" << v << "] = ";
  // modo stupido O(n^2)
  int ans = 1e9;
  for (int u : c[cmp[v]]) {
    fill(d.begin(), d.end(), 0);
    dfs(u, gty++);
    ans = min(ans, *max_element(d.begin(), d.end()));
  }
  // cout << ans << "\n";
  return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  g.resize(N);
  d.resize(N);
  p.resize(N, -1);
  vis.resize(N, -1);
  cmp.resize(N, -1);
  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]});
  }
  for (int i = 0; i < N; ++i) {
    if (cmp[i] == -1) {
      c.push_back(vector<int>(0));
      dfs1(i);
      ++gty;
    }
  }
  int kek = gty;
  int ans = 0;
  for (int i = 0; i < kek; ++i)
    ans = max(ans, diam(c[i][0]));
  array<int, 3> o{};
  for (int i = 0; i < kek; ++i) {
    o[2] = max(o[2], coda(c[i][0]));
    if (o[1] < o[2]) swap(o[1], o[2]);
    if (o[0] < o[1]) swap(o[0], o[1]);
  }
  // cout << o[0] << " " << o[1] << " " << o[2] << "\n";
  if (gty == 1) return ans;
  ans = max(ans, o[0] + o[1] + L);
  if (gty == 2) return ans;
  ans = max(ans, o[1] + o[2] + 2*L);
  return ans;
}

#ifdef LORENZO
int main() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

  int n, m, l;
  cin >> n >> m >> l;
  int a[100], b[100], t[100];
  for (int i = 0; i < m; ++i) cin >> a[i];
  for (int i = 0; i < m; ++i) cin >> b[i];
  for (int i = 0; i < m; ++i) cin >> t[i];
  cout << travelTime(n, m, l, a, b, t) << "\n";
}
#endif

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:22:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |   for (auto [u, w] : g[v])
      |             ^
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   for (auto [u, w] : g[v]) {
      |             ^
/usr/bin/ld: /tmp/ccX2qxgo.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status