제출 #839900

#제출 시각아이디문제언어결과실행 시간메모리
839900That_Salamander가장 긴 여행 (IOI23_longesttrip)C++17
15 / 100
988 ms2836 KiB
#include <vector> std::vector<int> longest_trip(int N, int D); bool are_connected(std::vector<int> A, std::vector<int> B); #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; int n; bool adj[256][256]; vector<int> conn[256]; vector<int> makePath(vector<int>& nodes); pair<vi, vi> makePaths(vector<int>& nodes) { if (nodes.size() <= 1) { return {nodes, {}}; } vi g1; vector<bool> mask(n, true); for (int x: nodes) { mask[x] = false; } queue<int> q; q.push(nodes[0]); while (!q.empty()) { auto t = q.front(); q.pop(); if (mask[t]) continue; g1.push_back(t); mask[t] = true; for (int c: conn[t]) { q.push(c); } } if (g1.size() == nodes.size()) { return {makePath(nodes), {}}; } else { vi g2; for (int x: nodes) { if (!mask[x]) { g2.push_back(x); } } return {g1, g2}; } } #define MIDDLE 0 #define INTER 1 #define UPPER 2 #define LOWER 3 vector<int> makePath(vector<int>& nodes) { if (nodes.size() <= 2) return nodes; vector<int> nodeTypes(n, -1); int middleNode = nodes[0]; nodeTypes[middleNode] = MIDDLE; vi lowerNodes, interNodes, upperNodes; for (int x: nodes) { if (nodeTypes[x] == -1 && !adj[x][middleNode]) { lowerNodes.push_back(x); nodeTypes[x] = LOWER; } } for (int x: nodes) { if (nodeTypes[x] != -1) continue; bool bruh = false; for (int y: lowerNodes) { if (adj[x][y]) { bruh = true; break; } } if (bruh) { interNodes.push_back(x); nodeTypes[x] = INTER; } else { upperNodes.push_back(x); nodeTypes[x] = UPPER; } } if (lowerNodes.size() == 0) { auto p = makePaths(upperNodes); vi res; for (int x: p.first) { res.push_back(x); } res.push_back(middleNode); for (int x: p.second) { res.push_back(x); } return res; } else if (lowerNodes.size() == 1) { vector<int> res(upperNodes.begin(), upperNodes.end()); res.push_back(middleNode); auto p = makePaths(interNodes); for (int x: p.first) { res.push_back(x); } res.push_back(lowerNodes[0]); for (int x: p.second) { res.push_back(x); } return res; } else { vector<int> res(upperNodes.begin(), upperNodes.end()); res.push_back(middleNode); auto p = makePaths(interNodes); for (int x: p.first) { res.push_back(x); } int n1 = p.first.back(); if (p.second.empty()) { int start; for (int x:lowerNodes) { if (adj[x][n1]) { start = x; break; } } res.push_back(start); for (int x:lowerNodes) { if (x != start) res.push_back(x); } } else { int n2 = p.second.front(); int a, b; vector<int> a1, a2; for (int x: lowerNodes) { if (adj[n1][x]) { a1.push_back(x); } if (adj[n2][x]) { a2.push_back(x); } } if (a1.size() > 1 && a2.size() > 1) { a = a1[0]; b = a2[0] == a ? a2[1] : a2[0]; } else if (a2.size() > 1) { a = a1[0]; b = a2[0] == a ? a2[1] : a2[0]; } else if (a1.size() > 1) { b = a2[0]; a = a1[0] == b ? a1[1] : a1[0]; } else { a = a1[0]; b = a2[0]; } out: res.push_back(a); for (int x: lowerNodes) { if (x != a && x != b) { res.push_back(x); } } res.push_back(a); for (int x: p.second) { res.push_back(x); } } return res; } } vector<int> longest_trip(int N, int D) { n = N; memset(adj, false, sizeof(adj)); for (int i = 0; i < N; i++) { conn[i].clear(); } vi allNodes; for (int i = 0; i < N; i++) { allNodes.push_back(i); for (int j = i+1; j < N; j++) { if (are_connected({i}, {j})) { adj[i][j] = adj[j][i] = true; conn[i].push_back(j); conn[j].push_back(i); } } } pair<vi, vi> res = makePaths(allNodes); if (res.first.size() > res.second.size()) { return res.first; } else { return res.second; } } #ifdef BRUH static inline constexpr int maxNumberOfCalls = 32640; static inline constexpr int maxTotalNumberOfCalls = 150000; static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000; static int call_counter = 0; static int total_call_counter = 0; static int landmark_counter = 0; static int C, N, D; static std::vector<std::vector<int>> U; static std::vector<bool> present; static inline void protocol_violation(std::string message) { printf("Protocol Violation: %s\n", message.c_str()); exit(0); } bool are_connected(std::vector<int> A, std::vector<int> B) { ++call_counter; ++total_call_counter; if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls) { protocol_violation("too many calls"); } int nA = A.size(), nB = B.size(); landmark_counter += nA + nB; if (landmark_counter > maxTotalNumberOfLandmarksInCalls) { protocol_violation("too many elements"); } if (nA == 0 || nB == 0) { protocol_violation("invalid array"); } for (int i = 0; i < nA; ++i) { if (A[i] < 0 || N <= A[i]) { protocol_violation("invalid array"); } if (present[A[i]]) { protocol_violation("invalid array"); } present[A[i]] = true; } for (int i = 0; i < nA; ++i) { present[A[i]] = false; } for (int i = 0; i < nB; ++i) { if (B[i] < 0 || N <= B[i]) { protocol_violation("invalid array"); } if (present[B[i]]) { protocol_violation("invalid array"); } present[B[i]] = true; } for (int i = 0; i < nB; ++i) { present[B[i]] = false; } for (int i = 0; i < nA; ++i) { for (int j = 0; j < nB; ++j) { if (A[i] == B[j]) { protocol_violation("non-disjoint arrays"); } } } for (int i = 0; i < nA; ++i) { for (int j = 0; j < nB; ++j) { if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1) { return true; } } } return false; } int main() { assert(1 == scanf("%d", &C)); int maximumCalls = 0; for (int c = 0; c < C; ++c) { call_counter = 0; assert(2 == scanf("%d %d", &N, &D)); present.assign(N, false); U.resize(N); for (int i = 1; i < N; ++i) { U[i].resize(i); for (int j = 0; j < i; ++j) { assert(1 == scanf("%d", &U[i][j])); } } for (int i = 2; i < N; ++i) { for (int j = 1; j < i; ++j) { for (int k = 0; k < j; ++k) { if (U[i][j] + U[i][k] + U[j][k] < D) { printf("Insufficient Density\n"); exit(0); } } } } std::vector<int> t = longest_trip(N, D); int l = t.size(); printf("%d\n", l); for (int i = 0; i < l; ++i) { printf(i == 0 ? "%d" : " %d", t[i]); } printf("\n"); printf("%d\n", call_counter); maximumCalls = std::max(maximumCalls, call_counter); call_counter = 0; } printf("%d\n", maximumCalls); return 0; } #endif

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

longesttrip.cpp: In function 'std::vector<int> makePath(std::vector<int>&)':
longesttrip.cpp:190:13: warning: label 'out' defined but not used [-Wunused-label]
  190 |             out:
      |             ^~~
#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...