Submission #945478

#TimeUsernameProblemLanguageResultExecution timeMemory
945478turtletortlesBurza (COCI16_burza)C++17
0 / 160
1081 ms504492 KiB
#include "bits/stdc++.h" #include <utility> using namespace std; #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define endl '\n' #define debug(x) std::cerr << #x << " = " << x << '\n'; template<typename T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } constexpr int MOD = 1e9 + 7; constexpr int INF = 0x3f3f3f3f; constexpr long long LLINF = 0x3f3f3f3f3f3f3f3f; const int MAXN = 405; vector<int> adj[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; if (k * k >= n) return cout << "DA" << endl, 0; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); adj[v].push_back(u); } vector<vector<int>> paths; queue<pair<vector<int>, int>> q; q.push({{0}, 0}); while (q.size()) { auto cur = q.front(); q.pop(); if (cur.first.size() == k + 1) { paths.push_back(cur.first); continue; } for (auto to : adj[cur.first.back()]) { if (to == cur.second) continue; vector<int> npath(cur.first); npath.emplace_back(to); q.push({npath, cur.first.back()}); } } vector<vector<int>> arr[k + 5]; vector<int> start(paths.size()); iota(all(start), 0); arr[0].push_back(start); for (int i = 0; i <= k; i++) { for (auto active : arr[i]) if (!active.size()) return cout << "DA" << endl, 0; set<int> s; for (auto active : arr[i]) for (auto path : active) s.insert(paths[path][i + 1]); for (auto off : s) { //construct new path without off for (auto active : arr[i]) { vector<int> nactive; for (auto path : active) if (paths[path][i + 1] != off) nactive.push_back(path); arr[i + 1].push_back(nactive); } } } cout << "NE" << endl; return 0; }

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:38:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     if (cur.first.size() == k + 1) {
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~
#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...
#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...