Submission #1066711

#TimeUsernameProblemLanguageResultExecution timeMemory
1066711LittleOrangeBeech Tree (IOI23_beechtree)C++17
9 / 100
2037 ms85796 KiB
#include "beechtree.h" #include<bits/stdc++.h> using namespace std; using ll = int; struct obj{ ll i,d; set<ll> s; bool operator<(const obj &o){ return d!=o.d?d<o.d:s.size()>o.s.size(); } bool nxt(const obj &o){ for(ll i : o.s){ if (!s.count(i)){ return false; } } return true; } }; std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) { ll n = N; ll m = M; vector<vector<ll>> ch(n); for(ll i = 1;i<n;i++) ch[P[i]].push_back(i); vector<ll> h(n,0),d(n,0); { function<void(ll)> dfs; dfs = [&](ll i){ for(ll j : ch[i]) { d[j] = d[i]+1; dfs(j); h[i] = max(h[i],h[j]+1); } }; dfs(0); } vector<ll> bad(n,0); for(ll i = n-1;i>=0;i--){ vector<ll> v; for(ll j : ch[i]){ if (bad[j]) bad[i] = 1; v.push_back(C[j]); if(ch[i].size()<ch[j].size()) bad[i] = 1; } sort(v.begin(),v.end()); if (unique(v.begin(),v.end())!=v.end()) bad[i] = 1; } vector<ll> ans(n,0); for(ll i = 0;i<n;i++){ if (bad[i]) continue; if (h[i]<=1) { ans[i] = 1; continue; } vector<obj> cur; function<void(ll)> dfs; dfs = [&](ll i){ if (ch[i].empty()) return; obj o = {i,d[i]}; for(ll j : ch[i]){ o.s.insert(C[j]); } cur.push_back(o); for(ll j : ch[i]){ dfs(j); } }; dfs(i); sort(cur.begin(),cur.end()); ll res = 1; for(ll i = 0;i+1<cur.size();i++){ if (!cur[i].nxt(cur[i+1])){ res = 0; break; } } ans[i] = res; } return ans; }

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:72:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(ll i = 0;i+1<cur.size();i++){
      |                      ~~~^~~~~~~~~~~
beechtree.cpp:23:8: warning: unused variable 'm' [-Wunused-variable]
   23 |     ll m = M;
      |        ^
#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...