Submission #720970

#TimeUsernameProblemLanguageResultExecution timeMemory
720970qwerasdfzxclMeetings (JOI19_meetings)C++17
29 / 100
3044 ms15372 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int mp[2020][2020], qcnt; int query(int x, int y, int z){ if (x==1){ if (y > z) swap(y, z); if (mp[y][z]) return mp[y][z]; assert(qcnt++ <= 100000); return mp[y][z] = Query(x-1, y-1, z-1) + 1; } return Query(x-1, y-1, z-1) + 1; } void answer(int x, int y){ if (x > y) swap(x, y); Bridge(x-1, y-1); } void dfs(int s, const vector<int> &a){ vector<vector<int>> subtree; for (const auto &x:a){ bool flag = 0; for (auto &V:subtree){ if (query(1, x, V[0])!=s){ flag = 1; V.push_back(x); break; } } if (flag) continue; subtree.emplace_back(); subtree.back().push_back(x); } for (auto &V:subtree){ vector<int> C = V; while(C.size() > 1){ int x = C.back(); C.pop_back(); int y = C.back(); C.pop_back(); int z = query(1, x, y); if (x==z) C.push_back(x); if (y==z) C.push_back(y); } answer(s, C[0]); V.erase(find(V.begin(), V.end(), C[0])); dfs(C[0], V); } } void Solve(int N) { vector<int> a; for (int i=2;i<=N;i++) a.push_back(i); dfs(1, a); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...