Submission #1256035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256035		comgaTramAnh	Dreaming (IOI13_dreaming)	C++20	Compilation error	0 ms	0 KiB

dreaming

#include <bits/stdc++.h> 
//#include "dreaming.h"
using namespace std;
vector <int> listVertex; 
vector <vector <pair <int, int>>> adj;
vector <bool> visited;
vector <int> f_out, f_in;
vector <vector <int>> prefix, suffix; 
void dfs_out(int u, int father) {
  listVertex.push_back(u); 
  vector <pair <int, int>> children; 
  visited[u] = true; 
  for (int i = 0; i < (int) adj[u].size(); i++) {
    pair <int, int> neighbor = adj[u][i]; 
    if (neighbor.first != father) {
      children.push_back(neighbor); 
    }
  }
  for (int i = 0; i < (int) children.size(); i++) {
    dfs_out(children[i].first, u);
    f_out[u] = max(f_out[u], f_out[children[i].first] + children[i].second);   
  }
  prefix[u].clear(); 
  prefix[u].resize((int) children.size() + 2); 
  prefix[u][0] = 0; 
  for (int i = 1; i <= (int) children.size(); i++) {
    prefix[u][i] = max(prefix[u][i - 1], f_out[children[i - 1].first] + children[i - 1].second);
  }
  suffix[u].clear(); 
  suffix[u].resize((int) children.size() + 2); 
  suffix[u][(int) children.size() + 1] = 0; 
  for (int i = (int) children.size(); i >= 1; i--) {
    suffix[u][i] = max(suffix[u][i + 1], f_out[children[i - 1].first] + children[i - 1].second);
  }
}
void dfs_in(int u, int father) {
  vector <pair <int, int>> children; 
  for (int i = 0; i < (int) adj[u].size(); i++) {
    pair <int, int> neighbor = adj[u][i]; 
    if (neighbor.first == father) {
      continue; 
    }
    children.push_back(neighbor);
  }
  for (int i = 0; i < (int) children.size(); i++) {
    pair <int, int> neighbor = children[i];
    f_in[neighbor.first] = max(f_in[neighbor.first], f_in[u] + neighbor.second); 
    f_in[neighbor.first] = max(f_in[neighbor.first], max(prefix[u][i], suffix[u][i + 2]) + neighbor.second); 
    dfs_in(neighbor.first, u); 
  }
}
pair <int, int> solve(int u) {
  listVertex.clear();                        
  int n = (int) adj.size();
  dfs_out(u, -1);
  dfs_in(u, -1);
  int minDist = 1000000007;
  int ret;  
  for (int i = 0; i < (int) listVertex.size(); i++) {
    int u = listVertex[i]; 
    if (minDist > max(f_out[u], f_in[u])) {
      minDist = max(f_out[u], f_in[u]); 
      ret = u; 
    }   
  }  
  return make_pair(minDist, ret); 
}
int travelTime(int n, int m, int l, vector <int> a, vector <int> b, vector <int> t) {
  adj.resize(n);
  visited.resize(n, false);
  for (int i = 0; i < m; i++) {
    adj[a[i]].push_back(make_pair(b[i], t[i]));
    adj[b[i]].push_back(make_pair(a[i], t[i]));
  }
  int ans = 0; 
  f_out.resize(n, 0); 
  f_in.resize(n, 0);
  prefix.resize(n);
  suffix.resize(n);
  vector <pair <int, int>> save; 
  for (int i = 0; i < n; i++) {
    if (visited[i] == false) {        
      save.push_back(solve(i));
    }
  }
  sort(save.begin(), save.end()); 
  reverse(save.begin(), save.end()); 
  /*int minDist = 1000000007; 
  if ((int) save.size() >= 2) {
    for (int i = 0; i < (int) save.size(); i++) {
      int tmp;
      if (i != (int) save.size() - 1) {
        tmp = save[i].first + l + save.back().first;   
      }    
      else {
        tmp = save[i].first + l + save[(int) save.size() - 2].first; 
      }
      if ((int) save.size() > 2) {
        int large1 = -1, large2 = -1; 
        for (int j = (int) save.size() - 1; j >= 0; j--) {
          if (i != j) {
            if (large1 == -1) {
              large1 = j; 
            }
            else if (large2 == -1) {
              large2 = j; 
            }
            else {
              break; 
            }
          }
        }
        tmp = max(tmp, 2 * l + save[large1].first + save[large2].first); 
      }
      minDist = min(minDist, tmp); 
    }
  }                      */
  for (int u = 0; u < n; u++) {
    ans = max(ans, max(f_out[u], f_in[u])); 
  }
  if ((int) save.size() == 2) {
    ans = max(ans, save[0].first + save[1].first + l); 
  }         
  if ((int) save.size() > 2) {
    ans = max(ans, 2 * l + save[1].first + save[2].first);
  }
  return ans; 
}
/*int main() {
  cout << travelTime(12, 8, 2, {0, 8, 2, 5, 5, 1, 1, 10}, {8, 2, 7, 11, 1, 3, 9, 6}, {4, 2, 4, 3, 7, 1, 5, 3}); 
  system("pause");
  return 0; 
} */

Compilation message (stderr)

/usr/bin/ld: /tmp/ccbm2q4P.o: in function `main':
grader.c:(.text.startup+0xc4): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status