Submission #1203999

#TimeUsernameProblemLanguageResultExecution timeMemory
1203999Ghulam_JunaidPark (JOI17_park)C++20
10 / 100
103 ms2868 KiB
#include <bits/stdc++.h> #include "park.h" // #include "grader.cpp" using namespace std; static int Place[1400]; const int MXN = 1405; int n, par[MXN]; vector<int> g[MXN]; vector<pair<int, int>> edges; int Query(int u, int v){ Place[u] = Place[v] = 1; if (u > v) swap(u, v); int res = Ask(u, v, Place); memset(Place, 0, sizeof Place); return res; } void get_path(int u, int v){ vector<int> nodes; for (int x = 0; x < n; x ++){ if (x == u or x == v) continue; nodes.push_back(x); } if (Query(u, v)){ g[u].push_back(v); g[v].push_back(u); edges.push_back({u, v}); par[v] = u; return ; } int lo = -1; int hi = nodes.size() - 1; while (hi - lo > 1){ int mid = (lo + hi) / 2; for (int i = 0; i <= mid; i ++) Place[nodes[i]] = 1; if (Query(u, v)) hi = mid; else lo = mid; } get_path(u, nodes[hi]); get_path(nodes[hi], v); } void Detect(int T, int nn) { n = nn; memset(par, -1, sizeof par); memset(Place, 0, sizeof Place); int ep = 0, deg = 0; for (int v = 0; v < n; v ++){ if (v == ep) continue; deg += Query(ep, v); } if (deg != 1) ep = n - 1; for (int v = 0; v < n; v ++){ if (g[v].size() or v == ep) continue; get_path(ep, v); ep = v; } for (auto [u, v] : edges) Answer(min(u, v), max(u, v)); }
#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...