oj.uz

Submission #1044340

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

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

const ll B = 250;

struct mySet{
    map<ll,ll> sub;
    deque<ll> dq;
    ll sz = 0;
};

mySet st[100010];
ll id[100010];
vector<ll> g[100010];
ll dep[100010];
ll l[100010];
ll par[100010];
vector<pair<ll,ll>> vec[100010];
map<ll,ll> cnt[100010];
vector<ll> large;
ll down[100010];

void Merge(mySet &u, mySet &v, ll cdep) {
    while (u.dq.size() < v.dq.size()) u.dq.push_back(0);
    for (ll 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;
}

ll pv;
ll chk[100010];
ll ans[100010];
ll tme[100010];
ll poss[100010];

ll dfs(ll 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;
            if (st[id[x]].sub.find(l[x]) != st[id[x]].sub.end())
                ans[x] -= st[id[x]].sub[l[x]];
        }
        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) {
            assert(0);
            if (d < dep[x] || d > down[x]) continue;
            ll temp = min(cnt[l[x]][d], st[id[x]].dq[d - dep[x]]);
            ans[x] += temp;
        }
    }
    
    return id[x];
}

ll in[100010], out[100010];
ll pv2;

void dfs2(ll 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<ll> t[100010];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll N, K;
    cin >> N >> K;
    for (ll i=0; i<N; i++) {
        cin >> l[i];
    }
    for (ll i=1; i<N; i++) {
        cin >> par[i];
        g[par[i]].push_back(i);
    }
    dep[1] = 0;
    dfs2(0);
    ll mxdep = 0;
    for (ll i=0; i<N; i++) {
        t[dep[i]].push_back(l[i]);
        mxdep = max(mxdep, dep[i]);
    }
    for (ll 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 (ll 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 ++;
        }
    }
    
    for (ll 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<ll>> qrs(K);
    for (ll i=0; i<N; i++) {
        if (vec[dep[i]].size() < B)
            qrs[l[i]].push_back(i); 
    }
    seg.init(mxdep + 1);
    for (ll 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 (ll 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);
        }
    }
    ll mx = -1, mn = 0;
    for (ll 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&, ll)':
Main.cpp:29:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (ll i=0; i<v.dq.size(); i++) {
      |                  ~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:173:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for (ll j=1; j<t[i].size(); j++) {
      |                      ~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 91352 KB Output is correct
2 Correct 31 ms 93600 KB Output is correct
3 Correct 35 ms 93400 KB Output is correct
4 Correct 38 ms 93456 KB Output is correct
5 Correct 40 ms 93524 KB Output is correct
6 Correct 34 ms 93580 KB Output is correct
7 Correct 36 ms 93532 KB Output is correct
8 Correct 37 ms 94156 KB Output is correct
9 Correct 111 ms 125032 KB Output is correct
10 Correct 32 ms 93520 KB Output is correct
11 Correct 35 ms 94036 KB Output is correct
12 Correct 92 ms 122820 KB Output is correct
13 Correct 44 ms 93524 KB Output is correct
14 Correct 31 ms 94184 KB Output is correct
15 Correct 121 ms 126048 KB Output is correct
16 Correct 30 ms 93536 KB Output is correct

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 91448 KB Output is correct
2 Correct 30 ms 93480 KB Output is correct
3 Correct 33 ms 93628 KB Output is correct
4 Correct 34 ms 94048 KB Output is correct
5 Correct 84 ms 122760 KB Output is correct
6 Correct 35 ms 93596 KB Output is correct
7 Correct 38 ms 94208 KB Output is correct
8 Correct 89 ms 126888 KB Output is correct
9 Correct 36 ms 93572 KB Output is correct
10 Correct 39 ms 93940 KB Output is correct
11 Correct 119 ms 113276 KB Output is correct
12 Incorrect 55 ms 103008 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 33 ms 91552 KB Output is correct
2 Correct 35 ms 93560 KB Output is correct
3 Correct 35 ms 93416 KB Output is correct
4 Correct 36 ms 93408 KB Output is correct
5 Correct 38 ms 93344 KB Output is correct
6 Correct 35 ms 93596 KB Output is correct
7 Correct 34 ms 93640 KB Output is correct
8 Correct 118 ms 124944 KB Output is correct
9 Correct 38 ms 93396 KB Output is correct
10 Correct 37 ms 94152 KB Output is correct
11 Correct 122 ms 126068 KB Output is correct
12 Correct 50 ms 93572 KB Output is correct
13 Correct 34 ms 93596 KB Output is correct
14 Correct 38 ms 93448 KB Output is correct
15 Runtime error 117 ms 189856 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 91564 KB Output is correct
2 Correct 29 ms 93504 KB Output is correct
3 Correct 49 ms 93508 KB Output is correct
4 Correct 33 ms 93528 KB Output is correct
5 Correct 32 ms 93552 KB Output is correct
6 Correct 37 ms 93516 KB Output is correct
7 Correct 35 ms 93524 KB Output is correct
8 Correct 36 ms 94036 KB Output is correct
9 Correct 36 ms 93644 KB Output is correct
10 Correct 42 ms 94180 KB Output is correct
11 Correct 34 ms 93408 KB Output is correct
12 Correct 33 ms 94036 KB Output is correct
13 Correct 38 ms 93524 KB Output is correct
14 Correct 33 ms 94096 KB Output is correct
15 Correct 36 ms 93580 KB Output is correct
16 Correct 30 ms 93880 KB Output is correct
17 Correct 32 ms 93532 KB Output is correct
18 Incorrect 33 ms 93532 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 30 ms 91352 KB Output is correct
2 Correct 31 ms 93600 KB Output is correct
3 Correct 35 ms 93400 KB Output is correct
4 Correct 38 ms 93456 KB Output is correct
5 Correct 40 ms 93524 KB Output is correct
6 Correct 34 ms 93580 KB Output is correct
7 Correct 36 ms 93532 KB Output is correct
8 Correct 37 ms 94156 KB Output is correct
9 Correct 111 ms 125032 KB Output is correct
10 Correct 32 ms 93520 KB Output is correct
11 Correct 35 ms 94036 KB Output is correct
12 Correct 92 ms 122820 KB Output is correct
13 Correct 44 ms 93524 KB Output is correct
14 Correct 31 ms 94184 KB Output is correct
15 Correct 121 ms 126048 KB Output is correct
16 Correct 30 ms 93536 KB Output is correct
17 Correct 40 ms 91448 KB Output is correct
18 Correct 30 ms 93480 KB Output is correct
19 Correct 33 ms 93628 KB Output is correct
20 Correct 34 ms 94048 KB Output is correct
21 Correct 84 ms 122760 KB Output is correct
22 Correct 35 ms 93596 KB Output is correct
23 Correct 38 ms 94208 KB Output is correct
24 Correct 89 ms 126888 KB Output is correct
25 Correct 36 ms 93572 KB Output is correct
26 Correct 39 ms 93940 KB Output is correct
27 Correct 119 ms 113276 KB Output is correct
28 Incorrect 55 ms 103008 KB Output isn't correct
29 Halted 0 ms 0 KB -