oj.uz

Submission #1044301

# Submission time Handle Problem Language Result Execution time Memory
1044301 2024-08-05T08:43:15 Z 정민찬(#11007) Team Coding (EGOI24_teamcoding) C++17
12 / 100
 112 ms 121564 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, bool f = false) {
    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, x == 6);
    }
    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 (!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]];
        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, bool)':
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 28 ms 89172 KB Output is correct
2 Correct 28 ms 89164 KB Output is correct
3 Correct 30 ms 89180 KB Output is correct
4 Correct 32 ms 89176 KB Output is correct
5 Correct 30 ms 89172 KB Output is correct
6 Correct 32 ms 89180 KB Output is correct
7 Correct 32 ms 89220 KB Output is correct
8 Correct 32 ms 89692 KB Output is correct
9 Correct 102 ms 117256 KB Output is correct
10 Correct 31 ms 89160 KB Output is correct
11 Correct 34 ms 89684 KB Output is correct
12 Correct 82 ms 114816 KB Output is correct
13 Correct 31 ms 89172 KB Output is correct
14 Correct 29 ms 89692 KB Output is correct
15 Correct 99 ms 118828 KB Output is correct
16 Correct 31 ms 89172 KB Output is correct

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 89172 KB Output is correct
2 Correct 39 ms 89168 KB Output is correct
3 Correct 40 ms 89168 KB Output is correct
4 Correct 31 ms 89596 KB Output is correct
5 Correct 82 ms 114812 KB Output is correct
6 Correct 37 ms 89172 KB Output is correct
7 Correct 31 ms 89936 KB Output is correct
8 Correct 77 ms 121564 KB Output is correct
9 Correct 30 ms 89168 KB Output is correct
10 Correct 32 ms 89432 KB Output is correct
11 Correct 93 ms 105164 KB Output is correct
12 Incorrect 53 ms 95952 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 89180 KB Output is correct
2 Correct 29 ms 89180 KB Output is correct
3 Correct 31 ms 89176 KB Output is correct
4 Correct 32 ms 89180 KB Output is correct
5 Correct 29 ms 89228 KB Output is correct
6 Correct 31 ms 89076 KB Output is correct
7 Correct 31 ms 89180 KB Output is correct
8 Correct 99 ms 117580 KB Output is correct
9 Correct 29 ms 89180 KB Output is correct
10 Correct 31 ms 89836 KB Output is correct
11 Correct 112 ms 118568 KB Output is correct
12 Correct 28 ms 89200 KB Output is correct
13 Correct 30 ms 89176 KB Output is correct
14 Incorrect 32 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 40 ms 89164 KB Output is correct
2 Correct 32 ms 89276 KB Output is correct
3 Correct 34 ms 89180 KB Output is correct
4 Correct 28 ms 89292 KB Output is correct
5 Correct 28 ms 89152 KB Output is correct
6 Correct 29 ms 89180 KB Output is correct
7 Correct 32 ms 89168 KB Output is correct
8 Correct 31 ms 89688 KB Output is correct
9 Correct 29 ms 89180 KB Output is correct
10 Correct 29 ms 89680 KB Output is correct
11 Correct 32 ms 89224 KB Output is correct
12 Correct 31 ms 89900 KB Output is correct
13 Correct 27 ms 89172 KB Output is correct
14 Correct 30 ms 89936 KB Output is correct
15 Correct 29 ms 89180 KB Output is correct
16 Correct 34 ms 89428 KB Output is correct
17 Correct 34 ms 89156 KB Output is correct
18 Incorrect 30 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 28 ms 89172 KB Output is correct
2 Correct 28 ms 89164 KB Output is correct
3 Correct 30 ms 89180 KB Output is correct
4 Correct 32 ms 89176 KB Output is correct
5 Correct 30 ms 89172 KB Output is correct
6 Correct 32 ms 89180 KB Output is correct
7 Correct 32 ms 89220 KB Output is correct
8 Correct 32 ms 89692 KB Output is correct
9 Correct 102 ms 117256 KB Output is correct
10 Correct 31 ms 89160 KB Output is correct
11 Correct 34 ms 89684 KB Output is correct
12 Correct 82 ms 114816 KB Output is correct
13 Correct 31 ms 89172 KB Output is correct
14 Correct 29 ms 89692 KB Output is correct
15 Correct 99 ms 118828 KB Output is correct
16 Correct 31 ms 89172 KB Output is correct
17 Correct 38 ms 89172 KB Output is correct
18 Correct 39 ms 89168 KB Output is correct
19 Correct 40 ms 89168 KB Output is correct
20 Correct 31 ms 89596 KB Output is correct
21 Correct 82 ms 114812 KB Output is correct
22 Correct 37 ms 89172 KB Output is correct
23 Correct 31 ms 89936 KB Output is correct
24 Correct 77 ms 121564 KB Output is correct
25 Correct 30 ms 89168 KB Output is correct
26 Correct 32 ms 89432 KB Output is correct
27 Correct 93 ms 105164 KB Output is correct
28 Incorrect 53 ms 95952 KB Output isn't correct
29 Halted 0 ms 0 KB -