제출 #841312

#제출 시각아이디문제언어결과실행 시간메모리
841312I_love_Hoang_Yen가장 긴 여행 (IOI23_longesttrip)C++17
85 / 100
17 ms428 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; // Subtask 1: D == 3 vector<int> sub1(int n) { vector<int> res(n); std::iota(res.begin(), res.end(), 0); return res; } // Subtask 2: D == 2 bool has_edge(int u, int v) { return are_connected({u}, {v}); } vector<int> sub2(int n) { vector<int> res {0}; for (int i = 1; i < n; i++) { if (has_edge(0, i)) { res.push_back(i); break; } } for (int i = 1; i < n; i++) { if (i == res[1]) continue; if (has_edge(res.back(), i)) { res.push_back(i); } else { res.insert(res.begin(), i); } } return res; } // Subtask 3: D == 1, return path with length >= Lmax / 2 vector<int> sub3(int n) { // maintain 2 paths vector<int> p1 {0}, p2 {1}; for (int i = 2; i < n; ++i) { // consider p1.back(), p2.back(), i // -> there's at least 1 edge if (has_edge(p1.back(), i)) { p1.push_back(i); } else if (has_edge(p2.back(), i)) { p2.push_back(i); } else { reverse(p2.begin(), p2.end()); p1.insert(p1.end(), p2.begin(), p2.end()); p2 = {i}; } } if (p1.size() > p2.size()) return p1; return p2; } // Subtask 4: D == 1 vector<int> sub4(int n) { // Use subtask 3 to get 2 paths {{{ vector<int> p1 {0}, p2 {1}; for (int i = 2; i < n; ++i) { if (has_edge(p1.back(), i)) { p1.push_back(i); } else if (has_edge(p2.back(), i)) { p2.push_back(i); } else { reverse(p2.begin(), p2.end()); p1.insert(p1.end(), p2.begin(), p2.end()); p2 = {i}; } } // }}} // Make p1 longer path if (p1.size() < p2.size()) swap(p1, p2); if (p2.empty()) return p1; // Impossible to merge 2 paths if (!are_connected(p1, p2)) { return p1; } // Merge 2 paths: // Consider: p1[0], p1.back() and p2[0] -> at least 1 edge if (has_edge(p1.back(), p2[0])) { p1.insert(p1.end(), p2.begin(), p2.end()); return p1; } else if (has_edge(p1[0], p2[0])) { reverse(p2.begin(), p2.end()); p2.insert(p2.end(), p1.begin(), p1.end()); return p2; } // p1 is now a circle // corner case: |p2| == 1 if (p2.size() == 1) { for (int i = 0; i < p1.size(); ++i) { if (has_edge(p1[i], p2[0])) { reverse(p2.begin(), p2.end()); p2.insert(p2.end(), p1.begin() + i, p1.end()); p2.insert(p2.end(), p1.begin(), p1.begin() + i); return p2; } } } // Consider: p2[0], p2.back() and p1[0] -> at least 1 edge if (has_edge(p2[0], p1[0])) { reverse(p1.begin(), p1.end()); p1.insert(p1.end(), p2.begin(), p2.end()); return p1; } else if (has_edge(p2.back(), p1[0])) { p2.insert(p2.end(), p1.begin(), p1.end()); return p2; } // p2 is now also a circle // Find one edge from p1 -> p2 int l1 = 0, r1 = p1.size() - 1; // p1[l1..r1] has at least one edge to p2 while (l1 < r1) { int mid = (l1 + r1) / 2; if (are_connected(vector<int> (p1.begin() + l1, p1.begin() + mid + 1), p2)) { r1 = mid; } else l1 = mid + 1; } for (int i = l1; i <= l1; i++) { for (int j = 0; j < p2.size(); j++) { if (has_edge(p1[i], p2[j])) { vector<int> res; res.insert(res.end(), p1.begin() + i + 1, p1.end()); res.insert(res.end(), p1.begin(), p1.begin() + i + 1); res.insert(res.end(), p2.begin() + j, p2.end()); res.insert(res.end(), p2.begin(), p2.begin() + j); return res; } } } return p1; } vector<int> longest_trip(int n, int d) { if (d == 3) return sub1(n); if (d == 2) return sub2(n); return sub4(n); }

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> sub4(int)':
longesttrip.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < p1.size(); ++i) {
      |                         ~~^~~~~~~~~~~
longesttrip.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for (int j = 0; j < p2.size(); j++) {
      |                         ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...