oj.uz

Submission #858553

# Submission time Handle Problem Language Result Execution time Memory
858553 2023-10-08T17:52:22 Z ikura355 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 18 ms 1000 KB 
#include "longesttrip.h"

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

vector<int> solve3(int n) {
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);
  return ans;
}

vector<int> solve2(int n) {
  vector<int> nxt(n);
  int pair;
  for (int i = 1; i < n; i++)
    if (are_connected({0}, {i})) pair = i;
  int head = 0, tail = pair;
  nxt[head] = pair;
  for (int i = 0; i < n; i++) {
    if (i == 0 || i == pair) continue;
    if (are_connected({head}, {i})) {
      nxt[i] = head;
      head = i;
    } else {
      nxt[tail] = i;
      tail = i;
    }
  }
  vector<int> ans;
  while (true) {
    ans.push_back(head);
    if (head == tail) break;
    head = nxt[head];
  }
  return ans;
}

int get_connected(vector<int> x, vector<int> y) {
  if (x.empty() || y.empty()) return 0;
  return are_connected(x, y);
}

vector<int> solve1(int n) {
  vector<int> a({0}), b;
  for (int i = 1; i < n; i++) {
    int connect_a = get_connected(a, {i});
    int connect_b = get_connected(b, {i});
    if (!connect_a && !connect_b) {
      a.insert(a.end(), b.begin(), b.end());
      b = {i};
    } else {
      if (connect_b) swap(a, b);
      // head
      if (are_connected({a[0]}, {i})) a.insert(a.begin(), i);
      // tail
      else if (are_connected({a[a.size() - 1]}, {i}))
        a.push_back(i);
      else {
        for (int j = 0; j < (int)a.size(); j++) {
          if (are_connected({a[j]}, {i})) {
            // [i] + [j, ...] + [0, ..., j-1]
            vector<int> vec;
            vec.push_back(i);
            for (int k = j; k < (int)a.size(); k++) vec.push_back(a[k]);
            for (int k = 0; k < j; k++) vec.push_back(a[k]);
            break;
          }
        }
      }
    }
  }
  if (a.size() > b.size()) return a;
  return b;
}

std::vector<int> longest_trip(int n, int density) {
  if (density == 3) return solve3(n);
  if (density == 2) return solve2(n);
  if (density == 1) return solve1(n);
  return {};
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> solve2(int)':
longesttrip.cpp:18:13: warning: 'pair' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |   nxt[head] = pair;

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 4 ms 500 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 9 ms 344 KB Output is correct
5 Correct 8 ms 600 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 8 ms 344 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 8 ms 344 KB Output is correct
10 Correct 8 ms 344 KB Output is correct
11 Correct 8 ms 436 KB Output is correct
12 Correct 8 ms 344 KB Output is correct
13 Correct 8 ms 600 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 10 ms 432 KB Output is correct
4 Correct 14 ms 956 KB Output is correct
5 Correct 17 ms 496 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 10 ms 596 KB Output is correct
8 Correct 10 ms 344 KB Output is correct
9 Correct 11 ms 444 KB Output is correct
10 Correct 16 ms 748 KB Output is correct
11 Correct 17 ms 748 KB Output is correct
12 Correct 18 ms 984 KB Output is correct
13 Correct 16 ms 740 KB Output is correct
14 Correct 7 ms 344 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Incorrect 4 ms 596 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 9 ms 344 KB Output is correct
4 Correct 12 ms 612 KB Output is correct
5 Partially correct 16 ms 1000 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -