제출 #1124792

#제출 시각아이디문제언어결과실행 시간메모리
1124792salmonTeam Coding (EGOI24_teamcoding)C++20
42 / 100
4094 ms47988 KiB
#include <bits/stdc++.h> using namespace std; int N; int K; int lst[100100]; int parent[100100]; vector<int> children[100100]; int num[100100]; vector<int> srt; vector<int> lc[100100]; const int B = 500; int pre[100100]; int post[100100]; int d[100100]; int cont = 0; int templst[100100]; bool lo[100100]; pair<int,int> ans; void dfs(int i, int de){ d[i] = de; pre[i] = cont; cont++; for(int j : children[i]){ dfs(j,de + 1); } post[i] = cont - 1; } vector<int>* solve(int i){ vector<vector<int>*> v; pair<int,int> p = {0,-1}; vector<int>* vec = new vector<int>(); for(int j : children[i]){ v.push_back(solve(j)); p = max(p,make_pair( (int) (v.back() -> size()), (int)v.size() - 1 )); } if(v.empty()){ vec -> push_back(1); } else{ vec = v[p.second]; for(int j = 0; j < v.size(); j++){ if(j == p.second) continue; int it = vec -> size() - 1; while(! (v[j] -> empty()) ){ (*vec)[it] += v[j] -> back(); v[j] -> pop_back(); it--; } } vec -> push_back(1); } if(lo[lst[i]]){ int k = lst[i]; int ans = 0; int ans1 = 0; for(int j : lc[k]){ if(pre[i] <= pre[j] && pre[j] <= post[i]) ans1++; templst[d[j]]++; } //printf("s: "); for(int a = d[i], it = vec -> size() - 1; it >= 0; a++,it--){ ans += min( (*vec)[it], templst[a]); //printf("%d ",templst[a]); } //printf("\n"); ans1 = ans - ans1; //printf("%d %d\n",ans,ans1); ::ans = max(::ans,{ans,-ans1}); for(int j : lc[k]){ templst[d[j]]--; } } return vec; } pair<vector<int>*,vector<int>*> solve1(int i, int k){ vector<vector<int>*> v; vector<vector<int>*> v1; pair<int,int> p = {0,-1}; vector<int>* vec = new vector<int>(); vector<int>* vec1 = new vector<int>(); for(int j : children[i]){ pair<vector<int>*,vector<int>*> ii = solve1(j,k); v.push_back(ii.first); v1.push_back(ii.second); p = max(p,make_pair( (int) (v.back() -> size()), (int)v.size() - 1 )); } if(v.empty()){ vec -> push_back(1); if(lst[i] == k) vec1 -> push_back(1); else vec1 -> push_back(0); } else{ vec = v[p.second]; for(int j = 0; j < v.size(); j++){ if(j == p.second) continue; int it = vec -> size() - 1; while(! (v[j] -> empty()) ){ (*vec)[it] += v[j] -> back(); v[j] -> pop_back(); it--; } } vec -> push_back(1); vec1 = v1[p.second]; for(int j = 0; j < v.size(); j++){ if(j == p.second) continue; int it = vec1 -> size() - 1; while(! (v1[j] -> empty()) ){ (*vec1)[it] += v1[j] -> back(); v1[j] -> pop_back(); it--; } } if(lst[i] == k) vec1 -> push_back(1); else vec1 -> push_back(0); } if(lst[i] == k){ int ans = 0; int ans1 = 0; for(int a = d[i], it = vec -> size() - 1; it >= 0; a++,it--){ ans += min( (*vec)[it], templst[a]); ans1 += (*vec1)[it]; } ans1 = ans - ans1; ::ans = max(::ans,{ans,-ans1}); } return {vec,vec1}; } int main(){ scanf(" %d",&N); scanf(" %d",&K); for(int i = 0; i < K; i++){ num[i] = 0; lo[i] = false; templst[i] = 0; } for(int i = 0; i < N; i++){ scanf(" %d",&lst[i]); num[lst[i]]++; lc[lst[i]].push_back(i); } parent[0] = -1; for(int i = 1; i < N; i++){ scanf(" %d",&parent[i]); children[parent[i]].push_back(i); } dfs(0,0); for(int i = 0; i < K; i++){ if(num[i] >= B){ srt.push_back(i); } else lo[i] = true; } ans = {0,-1}; solve(0); //printf("%d %d",ans.first,-ans.second); for(int i : srt){ for(int i = 0; i < N; i++){ templst[i] = 0; } for(int j : lc[i]){ templst[d[j]]++; } solve1(0,i); } printf("%d %d",ans.first,-ans.second); }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
Main.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:184:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         scanf(" %d",&parent[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
#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...