Submission #519519

#	Time	Username	Problem	Language	Result	Execution time	Memory
519519		Minhho	Biochips (IZhO12_biochips)	C++17	0 / 100	7 ms	9676 KiB

biochips

#define taskname "BIOCHIP"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 4e5+10;
const int maxk = 2e5 + 1;
struct iii {int ff, ss, tt;};
vector<int> adj[maxn];
int v[maxn], in[maxn], out[maxn], n, m, root, tme;
vector<int> bit[2];
iii qr[maxn];
int dp[maxk][501];
//dp[i][j]: choose j from the first i

void upd(int pos, int val, int id) {for (; pos<=2*n; pos+=(pos&-pos)) bit[id][pos] = max(bit[id][pos], val);}
int qry(int pos, int id) {int ans = 0; for (; pos; pos-=(pos&-pos)) ans = max(ans, bit[id][pos]); return ans;}

bool cmp(iii x, iii y) {return x.ss < y.ss;}

void DFS(int u)
{
    in[u] = ++tme;
    for (int v: adj[u]) DFS(v);
    out[u] = ++tme;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    cin>>n>>m;
    for (int i=1, x; i<=n; i++)
    {
        cin>>x>>v[i];
        if (!x) root = i;
        else adj[x].emplace_back(i);
    }
    bit[0].resize(n<<1|1);
    bit[1].resize(n<<1|1);
    DFS(root);
    for (int i=1; i<=n; i++) qr[i] = {in[i], out[i], v[i]};
    sort(qr+1, qr+n+1, cmp);
    for (int i=1; i<=m; i++)
    {
        for (int j=i; j<=n; j++)
        {
            int tmp = qry(qr[i].ff, 0);
            upd(qr[i].ss, tmp + qr[i].tt, 1);
        }
        swap(bit[0], bit[1]);
        bit[1].clear();
    }
    cout<<qry(n<<1, 0);
}

• Subtask 1: 0 / 100