Submission #1204000

#TimeUsernameProblemLanguageResultExecution timeMemory
1204000Ghulam_JunaidPark (JOI17_park)C++20
27 / 100
405 ms852 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], h[MXN]; vector<int> g[MXN], lvl[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); } int comp(int u, int v, vector<int> vec){ for (int i = 0; i < n; i ++) Place[i] = 1; for (int x : vec) Place[x] = 0; return Query(u, v); } void Detect(int T, int nn) { n = nn; memset(par, -1, sizeof par); memset(Place, 0, sizeof Place); for (int v = 1; v < n; v ++){ if (g[v].size()) continue; int anc = 0; while (1){ if (g[anc].empty() or comp(anc, v, g[anc])) break; int lo = -1, hi = g[anc].size() - 1; while (hi - lo > 1){ int mid = (lo + hi) / 2; vector<int> vec; for (int i = 0; i <= mid; i ++) vec.push_back(g[anc][i]); if (comp(anc, v, vec)) lo = mid; else hi = mid; } anc = g[anc][hi]; } get_path(anc, 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...