oj.uz

Submission #858549

# Submission time Handle Problem Language Result Execution time Memory
858549 2023-10-08T17:46:25 Z ikura355 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 10 ms 600 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;
}

vector<int> solve1(int n) {
  vector<int> a({0}), b;
  for (int i = 1; i < n; i++) {
    int connect_a = are_connected(a, {i});
    int connect_b = are_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> tmp(a.begin() + j, a.end());
            tmp.insert(tmp.end(), a.begin(), a.begin() + j);
            tmp.insert(tmp.begin(), i);
            a = tmp;
            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 Incorrect 0 ms 344 KB invalid array
2 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 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 6 ms 344 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 10 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 9 ms 600 KB Output is correct
11 Correct 9 ms 600 KB Output is correct
12 Correct 9 ms 440 KB Output is correct
13 Correct 9 ms 440 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB invalid array
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB invalid array
2 Halted 0 ms 0 KB -