Submission #849038

#TimeUsernameProblemLanguageResultExecution timeMemory
849038math_rabbit_1028Beech Tree (IOI23_beechtree)C++17
0 / 100
2058 ms74432 KiB
#include "beechtree.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int n, m; vector<int> p, c; vector<int> adj[202020], res; int sz[202020]; void getsz(int v) { sz[v] = 1; vector<pii> temp; for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i]; getsz(u); sz[v] += sz[u]; temp.push_back({sz[u], i}); } if (temp.size() == 0) return; sort(temp.begin(), temp.end(), greater<pii>()); swap(adj[v][temp[0].second], adj[v][0]); } vector< pair<pii, int> > merge(vector< pair<pii, int> > lge, vector< pair<pii, int> > sml) { int r = sml.begin()->second; vector< pair<pii, int> > res; priority_queue< pair<pii, int> > pq; pq.push({{sz[r], 0}, r}); while (!pq.empty()) { int now = pq.top().second; int pos = upper_bound(lge.begin(), lge.end(), pq.top()) - lge.begin(); // lge[pos - 1] <= now < lge[pos] res.push_back(pq.top()); pq.pop(); for (int j = 0; j < adj[now].size(); j++) { int u = adj[now][j]; pq.push({{sz[u], -pos}, u}); } } for (int i = 0; i < res.size(); i++) lge.push_back(res[i]); sort(lge.begin(), lge.end(), greater< pair<pii, int> >()); return lge; } vector< pair<pii, int> > solve(int v) { vector< pair<pii, int> > vec; vec.push_back({{sz[v], 0}, v}); for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i]; if (i == 0) { vec = solve(u); vec.insert(vec.begin(), {{sz[v], 0}, v}); } else vec = merge(vec, solve(u)); } map<int, int> cnt; for (int i = 1; i < sz[v]; i++) { int now = vec[i].second, par; if (cnt.find(c[now]) == cnt.end()) { par = vec[0].second; cnt.insert({c[now], 1}); } else { par = vec[cnt[c[now]]].second; cnt[c[now]]++; } if (par != p[now]) { res[v] = 0; } } /* cout << "v : " << v << "\n"; for (int i = 0; i < vec.size(); i++) cout << vec[i].second << " "; cout << "\n"; */ return vec; } vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) { n = N; m = M; p = P; c = C; for (int i = 1; i < n; i++) { adj[p[i]].push_back(i); } for (int i = 0; i < n; i++) res.push_back(1); getsz(0); solve(0); return res; }

Compilation message (stderr)

beechtree.cpp: In function 'void getsz(int)':
beechtree.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < adj[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<std::pair<std::pair<int, int>, int> > merge(std::vector<std::pair<std::pair<int, int>, int> >, std::vector<std::pair<std::pair<int, int>, int> >)':
beechtree.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < adj[now].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
beechtree.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < res.size(); i++) lge.push_back(res[i]);
      |                     ~~^~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<std::pair<std::pair<int, int>, int> > solve(int)':
beechtree.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < adj[v].size(); 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...
#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...