| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1044168 |
2024-08-05T07:47:11 Z |
정민찬(#11007) |
Team Coding (EGOI24_teamcoding) |
C++17 |
|
34 ms |
98396 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll B = 200;
struct mySet{
map<int,int> sub;
map<pair<int,int>, int> save;
set<pair<int,int>> ssave;
deque<int> dq;
int sz = 0;
};
mySet st[100010];
int id[100010];
vector<int> g[100010];
int dep[100010];
int l[100010];
int par[100010];
vector<pair<int,int>> vec[100010];
vector<int> t[100010];
map<int,int> cnt[100010];
vector<int> large;
int down[100010];
void Merge(mySet &u, mySet &v, int cdep) {
while (u.dq.size() < v.dq.size()) u.dq.push_back(0);
for (auto &[col, d] : v.ssave) {
if (u.save.find(make_pair(col, d)) != u.save.end()) {
u.save[make_pair(col, d)] ++;
continue;
}
if (vec[d].size() < B) {
if (cnt[col][d] > u.dq[d-cdep]) {
u.sub[col] -= cnt[col][d] - u.dq[d-cdep];
}
}
u.save[{col, d}] = 1;
u.ssave.insert({col, d});
}
for (int i=0; i<v.dq.size(); i++) {
if (vec[cdep + i].size() < B) {
for (auto &[k, col] : vec[cdep + i]) {
if (u.ssave.find({col, cdep + i}) != u.ssave.end()) continue;
if (k > u.dq[i]) {
u.sub[col] -= k - u.dq[i];
}
else break;
}
}
u.dq[i] += v.dq[i];
if (vec[cdep + i].size() < B) {
for (auto &[k, col] : vec[cdep + i]) {
if (u.ssave.find({col, cdep + i}) != u.ssave.end()) continue;
if (k > u.dq[i]) {
// sub.find()
u.sub[col] += k - u.dq[i];
}
else break;
}
}
}
u.sz += v.sz;
}
int pv;
int chk[100010];
int ans[100010];
int tme[100010];
int poss[100010];
int dfs(int x) {
if (g[x].empty()) {
id[x] = pv ++;
st[id[x]].dq.push_back(1);
st[id[x]].ssave.insert({l[x], dep[x]});
st[id[x]].save[{l[x], dep[x]}] = 1;
st[id[x]].sz = 1;
if (vec[dep[x]].size() < B) {
for (auto &[i, col] : vec[dep[x]]) {
if (col == l[x]) continue;
if (i > 1) {
st[id[x]].sub[col] += i - 1;
}
}
}
return id[x];
}
int cur = -1;
chk[l[x]] ++;
for (auto &y : g[x]) {
int child = dfs(y);
if (cur == -1) {
cur = child;
continue;
}
if (st[cur].sz < st[child].sz) swap(cur, child);
Merge(st[cur], st[child], dep[x] + 1);
}
id[x] = cur;
st[id[x]].dq.push_front(1);
st[id[x]].ssave.insert({l[x], dep[x]});
st[id[x]].save[{l[x], dep[x]}] = 1;
st[id[x]].sz ++;
if (vec[dep[x]].size() < B) {
for (auto &[i, col] : vec[dep[x]]) {
if (col == l[x]) continue;
if (i > 1) {
st[id[x]].sub[col] += i - 1;
}
}
}
chk[l[x]] --;
if (!chk[l[x]]) {
poss[x] = 1;
if (st[id[x]].sub.find(l[x]) != st[id[x]].sub.end())
ans[x] -= st[id[x]].sub[l[x]];
auto lit = st[id[x]].ssave.lower_bound(make_pair(l[x], -1));
auto rit = st[id[x]].ssave.upper_bound(make_pair(l[x], (int)1e9));
for (auto it=lit; it!=rit; it++) {
int tot = st[id[x]].save[{l[x], it->second}];
int temp = min(cnt[l[x]][it->second], st[id[x]].dq[it->second - dep[x]]);
ans[x] += temp - cnt[l[x]][it->second];
}
for (auto &d : large) {
if (d < dep[x] || d > down[x]) continue;
int tot = st[id[x]].save[{l[x], d}];
int temp = min(cnt[l[x]][d], st[id[x]].dq[d - dep[x]]);
ans[x] += temp;
}
}
return id[x];
}
int in[100010], out[100010];
int pv2;
void dfs2(int x) {
down[x] = dep[x];
in[x] = ++pv;
for (auto &y : g[x]) {
dep[y] = dep[x] + 1;
dfs2(y);
down[x] = max(down[x], down[y]);
}
out[x] = pv;
}
struct Fenwick{
vector<ll> tree;
void init(ll n) {
tree.assign(n+1, 0);
}
void upd(ll i, ll v, ll n) {
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
ll qry(ll i) {
ll ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
};
Fenwick seg;
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
int N, K;
cin >> N >> K;
for (int i=0; i<N; i++) {
cin >> l[i];
}
for (int i=1; i<N; i++) {
cin >> par[i];
g[par[i]].push_back(i);
}
dep[1] = 0;
dfs2(0);
int mxdep = 0;
for (int i=0; i<N; i++) {
t[dep[i]].push_back(l[i]);
mxdep = max(mxdep, dep[i]);
}
for (int i=0; i<=mxdep; i++) {
assert(!t[i].empty());
sort(t[i].begin(), t[i].end());
vec[i].push_back({1, t[i][0]});
for (int j=1; j<t[i].size(); j++) {
if (t[i][j] != vec[i].back().second) {
vec[i].push_back({1, t[i][j]});
}
else vec[i].back().first ++;
}
sort(vec[i].begin(), vec[i].end());
}
vector<vector<int>> qrs(K);
for (int i=0; i<=mxdep; i++) {
if (vec[i].size() < B) {
for (auto &[j, col] : vec[i]) {
cnt[col][i] = j;
}
}
else {
large.push_back(i);
}
}
for (int i=0; i<N; i++) {
if (vec[dep[i]].size() < B)
qrs[l[i]].push_back(i);
}
dfs(0);
seg.init(mxdep + 1);
for (int i=0; i<K; i++) {
for (auto &j : qrs[i]) {
seg.upd(dep[j]+1, 1, mxdep+1);
}
for (auto &j : qrs[i]) {
if (poss[j]) {
ans[j] += seg.qry(down[j]+1) - seg.qry(dep[j]);
}
}
for (auto &j : qrs[i]) {
seg.upd(dep[j]+1, -1, mxdep+1);
}
}
seg.init(N);
for (int i=0; i<K; i++) {
for (auto &j : qrs[i]) {
seg.upd(in[j], 1, N);
}
for (auto &j : qrs[i]) {
if (poss[j]) {
tme[j] = ans[j] - seg.qry(out[j]) + seg.qry(in[j]-1);
}
}
for (auto &j : qrs[i]) {
seg.upd(in[j], -1, N);
}
}
int mx = -1, mn = 0;
for (int i=0; i<N; i++) {
if (poss[i]) {
if (mx < ans[i]) {
mx = ans[i];
mn = tme[i];
}
else if (mx == ans[i] && mn > tme[i]) {
mn = tme[i];
}
}
}
cout << mx << ' ' << mn << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'void Merge(mySet&, mySet&, int)':
Main.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i=0; i<v.dq.size(); i++) {
| ~^~~~~~~~~~~~
Main.cpp: In function 'int dfs(int)':
Main.cpp:126:17: warning: unused variable 'tot' [-Wunused-variable]
126 | int tot = st[id[x]].save[{l[x], it->second}];
| ^~~
Main.cpp:132:17: warning: unused variable 'tot' [-Wunused-variable]
132 | int tot = st[id[x]].save[{l[x], d}];
| ^~~
Main.cpp: In function 'int main()':
Main.cpp:200:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int j=1; j<t[i].size(); j++) {
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
98384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
98272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
98396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
98396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
98384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
