Submission #943713

#TimeUsernameProblemLanguageResultExecution timeMemory
943713stefanneaguCat in a tree (BOI17_catinatree)C++17
51 / 100
68 ms22956 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 + 1; int k, sz[nmax], l[nmax]; vector<vector<int>> adj; void dfs(int i, int tata) { for(auto it : adj[i]) { if(it != tata) { dfs(it, i); } } int x = 1; vector<int> v; v.push_back(0); // daca pot sa bag la nodul i? for(auto it : adj[i]) { if(it != tata) { x += sz[it]; v.push_back(l[it]); } } sort(v.begin(), v.end()); int ind = 0; while(ind < v.size() - 1 && v[ind] + v[ind + 1] < k) { ind ++; x --; } l[i] = v[ind] + 1; sz[i] = x; } int main() { int n; cin >> n >> k; adj.resize(n + 1); for(int i = 2; i <= n; i ++) { int a; cin >> a; a ++; adj[a].push_back(i); adj[i].push_back(a); } dfs(1, 0); cout << sz[1]; return 0; }

Compilation message (stderr)

catinatree.cpp: In function 'void dfs(int, int)':
catinatree.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while(ind < v.size() - 1 && v[ind] + v[ind + 1] < k) {
      |         ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...