oj.uz

Submission #1044309

# Submission time Handle Problem Language Result Execution time Memory
1044309 2024-08-05T08:45:41 Z 정민찬(#11007) Team Coding (EGOI24_teamcoding) C++17
12 / 100
 134 ms 121052 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll B = 2e18;

struct mySet{
    map<int,int> sub;
    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];
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 (int i=0; i<v.dq.size(); i++) {
        if (vec[cdep + i].size() < B) {
            for (auto &[k, col] : vec[cdep + i]) {
                if (k > u.dq[i]) {
                    u.sub[col] -= k - u.dq[i];
                }
            }
        }
        u.dq[i] += v.dq[i];
        if (vec[cdep + i].size() < B) {
            for (auto &[k, col] : vec[cdep + i]) {
                if (k > u.dq[i]) {
                    // sub.find()
                    u.sub[col] += k - u.dq[i];
                }
            }
        }
    }
    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]].sz = 1;
        if (vec[dep[x]].size() < B) {
            for (auto &[i, col] : vec[dep[x]]) {
                if (i > 1) {
                    st[id[x]].sub[col] += i - 1;
                }
            }
        }
        if (!chk[l[x]]) {
            poss[x] = 1;
            ans[x] = 0;
        }
        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]].sz ++;
    if (vec[dep[x]].size() < B) {
        for (auto &[i, col] : vec[dep[x]]) {
            if (i > 1) {
                st[id[x]].sub[col] += i - 1;
            }
        }
    }
    chk[l[x]] --;
    if (true) {
        poss[x] = 1;
        if (st[id[x]].sub.find(l[x]) != st[id[x]].sub.end())
            ans[x] -= st[id[x]].sub[l[x]];
        for (auto &d : large) {
            if (d < dep[x] || d > down[x]) continue;
            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] = ++pv2;
    for (auto &y : g[x]) {
        dep[y] = dep[x] + 1;
        dfs2(y);
        down[x] = max(down[x], down[y]);
    }
    out[x] = pv2;
}

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;

vector<int> t[100010];

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());
    }
    
    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);
        }
    }
    
    dfs(0);
    vector<vector<int>> qrs(K);
    for (int i=0; i<N; i++) {
        if (vec[dep[i]].size() < B)
            qrs[l[i]].push_back(i); 
    }
    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:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<v.dq.size(); i++) {
      |                   ~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:171:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for (int j=1; j<t[i].size(); j++) {
      |                       ~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 89172 KB Output is correct
2 Correct 32 ms 89204 KB Output is correct
3 Correct 31 ms 89180 KB Output is correct
4 Correct 31 ms 89216 KB Output is correct
5 Correct 32 ms 89180 KB Output is correct
6 Correct 26 ms 89180 KB Output is correct
7 Correct 32 ms 89240 KB Output is correct
8 Correct 33 ms 89684 KB Output is correct
9 Correct 127 ms 117152 KB Output is correct
10 Correct 35 ms 89180 KB Output is correct
11 Correct 30 ms 89692 KB Output is correct
12 Correct 83 ms 114304 KB Output is correct
13 Correct 38 ms 89168 KB Output is correct
14 Correct 32 ms 89692 KB Output is correct
15 Correct 134 ms 118616 KB Output is correct
16 Correct 29 ms 89180 KB Output is correct

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 89156 KB Output is correct
2 Correct 32 ms 89172 KB Output is correct
3 Correct 33 ms 89176 KB Output is correct
4 Correct 32 ms 89692 KB Output is correct
5 Correct 84 ms 114300 KB Output is correct
6 Correct 33 ms 89172 KB Output is correct
7 Correct 32 ms 89888 KB Output is correct
8 Correct 77 ms 121052 KB Output is correct
9 Correct 31 ms 89180 KB Output is correct
10 Correct 29 ms 89436 KB Output is correct
11 Correct 91 ms 105764 KB Output is correct
12 Incorrect 61 ms 96460 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 89168 KB Output is correct
2 Correct 28 ms 89080 KB Output is correct
3 Correct 26 ms 89176 KB Output is correct
4 Correct 33 ms 89036 KB Output is correct
5 Correct 31 ms 89176 KB Output is correct
6 Correct 29 ms 89168 KB Output is correct
7 Correct 34 ms 89180 KB Output is correct
8 Correct 99 ms 116908 KB Output is correct
9 Correct 33 ms 89180 KB Output is correct
10 Correct 32 ms 89692 KB Output is correct
11 Correct 104 ms 118612 KB Output is correct
12 Correct 37 ms 89164 KB Output is correct
13 Correct 31 ms 89180 KB Output is correct
14 Incorrect 34 ms 89180 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 89168 KB Output is correct
2 Correct 34 ms 89176 KB Output is correct
3 Correct 32 ms 89080 KB Output is correct
4 Correct 32 ms 89180 KB Output is correct
5 Correct 33 ms 89168 KB Output is correct
6 Correct 34 ms 89180 KB Output is correct
7 Correct 32 ms 89180 KB Output is correct
8 Correct 33 ms 89680 KB Output is correct
9 Correct 36 ms 89056 KB Output is correct
10 Correct 32 ms 89692 KB Output is correct
11 Correct 32 ms 89168 KB Output is correct
12 Correct 30 ms 89692 KB Output is correct
13 Correct 30 ms 89180 KB Output is correct
14 Correct 30 ms 89944 KB Output is correct
15 Correct 31 ms 89176 KB Output is correct
16 Correct 35 ms 89604 KB Output is correct
17 Correct 31 ms 89068 KB Output is correct
18 Incorrect 31 ms 89180 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 89172 KB Output is correct
2 Correct 32 ms 89204 KB Output is correct
3 Correct 31 ms 89180 KB Output is correct
4 Correct 31 ms 89216 KB Output is correct
5 Correct 32 ms 89180 KB Output is correct
6 Correct 26 ms 89180 KB Output is correct
7 Correct 32 ms 89240 KB Output is correct
8 Correct 33 ms 89684 KB Output is correct
9 Correct 127 ms 117152 KB Output is correct
10 Correct 35 ms 89180 KB Output is correct
11 Correct 30 ms 89692 KB Output is correct
12 Correct 83 ms 114304 KB Output is correct
13 Correct 38 ms 89168 KB Output is correct
14 Correct 32 ms 89692 KB Output is correct
15 Correct 134 ms 118616 KB Output is correct
16 Correct 29 ms 89180 KB Output is correct
17 Correct 32 ms 89156 KB Output is correct
18 Correct 32 ms 89172 KB Output is correct
19 Correct 33 ms 89176 KB Output is correct
20 Correct 32 ms 89692 KB Output is correct
21 Correct 84 ms 114300 KB Output is correct
22 Correct 33 ms 89172 KB Output is correct
23 Correct 32 ms 89888 KB Output is correct
24 Correct 77 ms 121052 KB Output is correct
25 Correct 31 ms 89180 KB Output is correct
26 Correct 29 ms 89436 KB Output is correct
27 Correct 91 ms 105764 KB Output is correct
28 Incorrect 61 ms 96460 KB Output isn't correct
29 Halted 0 ms 0 KB -