Submission #697523

#	Time	Username	Problem	Language	Result	Execution time	Memory
697523		vuavisao	Magic Tree (CEOI19_magictree)	C++14	80 / 100	106 ms	40424 KiB

magictree

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const ll N = 1e5 + 10;

ll n, m, k;
vector<ll> g[N];

ll d[N], cost[N];
bool have[N];

namespace sub145 {
    bool check() {
        return (k <= 20);
    }

    ll dp[N][22];

    void dfs(ll u) {
        for(const auto& v : g[u]) {
            dfs(v);
            for(ll use = 0; use <= k; ++ use) {
                dp[u][use] += dp[v][use];
            }
        }
        if(have[u]) {
            dp[u][d[u]] += cost[u];
        }
        for(ll use = 1; use <= k; ++ use) dp[u][use] = max(dp[u][use], dp[u][use - 1]);
    }

    void solve() {
        dfs(1);
        cout << dp[1][k];
    }
}

namespace sub2 {
    bool check() {
        for(ll u = 1; u <= n; ++ u) {
            if(g[u].empty()) {
                if(!have[u]) return false;
            }
            else {
                if(have[u]) return false;
            }
        }
        return true;
    }

    void solve() {
        ll res = 0;
        for(ll u = 1; u <= n; ++ u) res += cost[u];
        cout << res;
    }
}

namespace sub3 {
    bool check() {
        for(ll u = 1; u < n; ++ u) {
            if((ll) g[u].size() != 1 || g[u][0] != u + 1) return false;
        }
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                if(cost[u] != 1) return false;
            }
        }
        return true;
    }

    ll tree[N];

    void update(ll idx, ll val) {
        for( ; idx <= k; idx += (idx & - idx)) tree[idx] = max(tree[idx], val);
    }

    ll query(ll idx) {
        ll res = 0;
        for( ; idx > 0; idx -= (idx & - idx)) res = max(res, tree[idx]);
        return res;
    }

    void compress() {
        vector<ll> Pos = {};
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                Pos.push_back(d[u]);
            }
        }
        sort(Pos.begin(), Pos.end());
        Pos.resize(unique(Pos.begin(), Pos.end()) - Pos.begin());
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                d[u] = lower_bound(Pos.begin(), Pos.end(), d[u]) - Pos.begin() + 1;
            }
        }
        k = (ll) Pos.size();
    }

    void solve() {
        compress();
        for(ll u = n; u >= 1; -- u) {
            if(have[u]) {
                ll len = query(d[u]) + 1;
                update(d[u], len);
            }
        }
        cout << query(k);
    }
}

namespace sub6 {
    bool check() {
        return (m <= 1000);
    }

    ll Lg, parent[20][N], dist[N];
    ll cnt, in[N], out[N];

    ll suff_indices[N];
    ll dp[2010][1010];

    void dfs(ll u) {
        in[u] = ++ cnt;
        for(const auto& v : g[u]) {
            parent[0][v] = u;
            dist[v] = dist[u] + 1;
            dfs(v);
        }
        out[u] = cnt;
    }

    ll lca(ll u, ll v) {
        if(dist[u] < dist[v]) swap(u, v);
        ll delta = dist[u] - dist[v];
        for(ll i = Lg; i >= 0; -- i) {
            if(delta >> i & 1) {
                u = parent[i][u];
            }
        }
        if(u == v) return u;
        for(ll i = Lg; i >= 0; -- i) {
            if(parent[i][u] == parent[i][v]) continue;
            u = parent[i][u];
            v = parent[i][v];
        }
        return parent[0][u];
    }

    bool inside(ll u, ll v) {
        return (in[u] <= in[v] && out[v] <= out[u]);
    }

    void compress(const vector<ll>& indices) {
        vector<ll> Pos = indices;
        sort(Pos.begin(), Pos.end());
        for(const auto& u : indices) {
            ll idx = lower_bound(Pos.begin(), Pos.end(), u) - Pos.begin() + 1;
            suff_indices[u] = idx;
        }
        Pos.clear();
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                Pos.push_back(d[u]);
            }
        }
        sort(Pos.begin(), Pos.end());
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                ll idx = lower_bound(Pos.begin(), Pos.end(), d[u]) - Pos.begin() + 1;
                d[u] = idx;
            }
        }
        k = (ll) Pos.size();
    }

    void dfs_calc(ll u) {
        for(const auto& v : g[u]) {
            dfs_calc(v);
            for(ll use = 0; use <= k; ++ use) {
                dp[suff_indices[u]][use] += dp[suff_indices[v]][use];
            }
        }
        if(have[u]) {
            dp[suff_indices[u]][d[u]] += cost[u];
        }
        for(ll use = 1; use <= k; ++ use) dp[suff_indices[u]][use] = max(dp[suff_indices[u]][use], dp[suff_indices[u]][use - 1]);
    }

    void solve() {
        dist[1] = 1; dfs(1);
        Lg = __lg(n);
        for(ll j = 1; j <= Lg; ++ j) {
            for(ll i = 1; i <= n; ++ i) {
                parent[j][i] = parent[j - 1][parent[j - 1][i]];
            }
        }
        for(ll u = 1; u <= n; ++ u) g[u].clear();
        vector<ll> indices = {};
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                indices.push_back(u);
            }
        }
        sort(indices.begin(), indices.end(), [&] (ll u, ll v) -> bool {
            return in[u] > in[v];
        });
        ll cnt = (ll) indices.size();
        for(ll i = 1; i < cnt; ++ i) indices.push_back(lca(indices[i - 1], indices[i]));
        sort(indices.begin(), indices.end(), [&] (ll u, ll v) -> bool {
            return in[u] > in[v];
        });
        indices.resize(unique(indices.begin(), indices.end()) - indices.begin());
        compress(indices);
        stack<ll> stk = {};
        for(const auto& u : indices) {
            while(!stk.empty() && inside(u, stk.top())) {
                ll v = stk.top(); stk.pop();
                g[u].push_back(v);
//                cout << u << ' ' << v << '\n';
            }
            stk.push(u);
        }
        dfs_calc(stk.top());
        cout << dp[suff_indices[stk.top()]][k];
    }
}

namespace sub7 {
    bool check() {
        for(ll u = 1; u <= n; ++ u) {
            if(have[u]) {
                if(cost[u] != 1) return false;
            }
        }
        return true;
    }

    multiset<ll> mst[N];
    ll res;

    void dfs(ll u) {
        ll big_child = - 1;
        for(const auto& v : g[u]) {
            dfs(v);
            if(big_child == - 1 || (ll) mst[v].size() > (ll) mst[big_child].size()) big_child = v;
        }
        if(big_child > - 1) {
            swap(mst[u], mst[big_child]);
        }
        for(const auto& v : g[u]) {
            if(v == big_child) continue;
            mst[u].insert(mst[v].begin(), mst[v].end());
        }
        if(have[u]) {
            auto psy = mst[u].upper_bound(d[u]);
            if(psy == mst[u].end()) {
                mst[u].insert(d[u]);
            }
            else {
                mst[u].erase(psy);
                mst[u].insert(d[u]);
            }
        }
        res = max(res, (ll) mst[u].size());
    }

    void solve() {
        dfs(1);
        cout << res;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("CEOI19_MAGICTREE.inp", "r")) {
        freopen("CEOI19_MAGICTREE.inp", "r", stdin);
        freopen("CEOI19_MAGICTREE.out", "w", stdout);
    }
    cin >> n >> m >> k;
    for(ll v = 2; v <= n; ++ v) {
        ll u; cin >> u;
        g[u].push_back(v);
//        cout << u << ' ' << v << '\n';
    }
    for(ll i = 1; i <= m; ++ i) {
        ll u; cin >> u >> d[u] >> cost[u];
        have[u] = true;
    }
    if(sub145::check()) {
        sub145::solve();
        return 0;
    }
    if(sub2::check()) {
        sub2::solve();
        return 0;
    }
    if(sub3::check()) {
        sub3::solve();
        return 0;
    }
    if(sub6::check()) {
        sub6::solve();
        return 0;
    }
    if(sub7::check()) {
        sub7::solve();
        return 0;
    }
//    sub8::solve();
    return 0;
}

/// Code by vuavisao

Compilation message (stderr)

magictree.cpp: In function 'int32_t main()':
magictree.cpp:282:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  282 |         freopen("CEOI19_MAGICTREE.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:283:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  283 |         freopen("CEOI19_MAGICTREE.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 0 / 17