Submission #841571

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
841571	2023-09-01 17:11:52	TheLostCookie	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	10 ms	856 KiB

longesttrip

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "longesttrip.h"
#include <functional>
#include <vector>
std::vector<int> longest_trip(int N, int D) {
  //Invariant: l0.back() and l1.back() are NOT connected.
  std::vector<int> l0,l1;
  
  auto mergeLines = [&l0, &l1]()->void{
    while(!l1.empty()) {
      l0.push_back(l1.back());
      l1.pop_back();
    }
    return;
  };
  
  auto q = [](int u, int v)->bool{
    return are_connected({u},{v});
  };
  
  l0.push_back(0);
  int u=1;
  while(u<N) {
    if(l1.empty()) {
      (q(l0.back(),u)?l0:l1).push_back(u);
      u++;
    } else if(u==N-1) {
      if(!q(l0.back(),u)) l1.push_back(u);
      else {
        l0.push_back(u);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60