Submission #938772

#TimeUsernameProblemLanguageResultExecution timeMemory
938772AdamGSBeech Tree (IOI23_beechtree)C++17
49 / 100
49 ms8584 KiB
#include "beechtree.h" #include<bits/stdc++.h> using namespace std; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e3+7; vector<pair<int,int>>V[LIM], K; int ile[LIM]; bool ok; void DFS(int x) { ile[x]=1; for(auto i : V[x]) { DFS(i.nd); ile[x]+=ile[i.nd]; } } void DFS2(int x) { for(int i=1; i<V[x].size(); ++i) if(V[x][i].st==V[x][i-1].st) ok=false; K.pb({ile[x], x}); for(auto i : V[x]) DFS2(i.nd); } bool zawiera(int a, int b) { if(V[a].size()>V[b].size()) return false; int l=0; rep(i, V[a].size()) { while(l<V[b].size() && V[b][l].st!=V[a][i].st) ++l; if(l==V[b].size()) return false; if(ile[V[a][i].nd]>ile[V[b][l].nd]) return false; } return true; } vector<int>beechtree(int n, int m, vector<int>P, vector<int>C) { rep(i, n-1) V[P[i+1]].pb({C[i+1], i+1}); rep(i, n) sort(all(V[i])); DFS(0); vector<int>ans(n); rep(i, n) { K.clear(); ok=true; DFS2(i); sort(all(K)); for(int j=1; j<K.size(); ++j) if(!zawiera(K[j-1].nd, K[j].nd)) ok=false; if(ok) ans[i]=1; } return ans; }

Compilation message (stderr)

beechtree.cpp: In function 'void DFS2(int)':
beechtree.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i=1; i<V[x].size(); ++i) if(V[x][i].st==V[x][i-1].st) ok=false;
      |                ~^~~~~~~~~~~~
beechtree.cpp: In function 'bool zawiera(int, int)':
beechtree.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
beechtree.cpp:28:3: note: in expansion of macro 'rep'
   28 |   rep(i, V[a].size()) {
      |   ^~~
beechtree.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(l<V[b].size() && V[b][l].st!=V[a][i].st) ++l;
      |           ~^~~~~~~~~~~~
beechtree.cpp:30:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if(l==V[b].size()) return false;
      |        ~^~~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int j=1; j<K.size(); ++j) if(!zawiera(K[j-1].nd, K[j].nd)) ok=false;
      |                  ~^~~~~~~~~
#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...