Submission #574438

#	Time	Username	Problem	Language	Result	Execution time	Memory
574438		saarang123	Biochips (IZhO12_biochips)	C++17	0 / 100	2106 ms	297644 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MXN = 200 * 1000 + 3;
const int MXM = 503;
int dp[MXN][MXM], a[MXN];
vector<int> g[MXN];
int n, m;

void dfs(int v) {
	for(int u : g[v]) {
		dfs(u);
		for(int i = m; i >= 0; i--)
			for(int j = 0; j <= i; j++) if(i - j >= 0 && dp[v][i - j] != -1 && dp[u][j] != -1)
				dp[v][i] = max(dp[v][i], dp[v][i - j] + dp[u][j]);
	}
	dp[v][1] = max(dp[v][1], a[v]);
}

// https://github.com/Aeren1564/Algorithms
template<bool Enable_small_to_large = true>
struct disjoint_set {
    int n, cc;
    vector<int> p;
    disjoint_set(int n): n(n), p(n, -1), cc(n) { }
    int root(int u) {
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b) {
        return root(a) == root(b);
    }
    int size(int u) {
        return -p[root(u)];
    }
    bool merge(int u, int v) {
        u = root(u), v = root(v);
        if(u == v) return false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u; cc--;
        return true;
    }
    void clear() {
        fill(p.begin(), p.end(), -1);
    }
    vector<vector<int>> group_up() {
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
};

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    cin >> n >> m;
    disjoint_set dsu(n);
    int r = -1;
    for(int p, i = 1; i <= n; i++) {
    	cin >> p >> a[i];
    	dp[i][0] = 0;
    	for(int j = 1; j <= m; j++)
    		dp[i][j] = -1;
    	if(p) {
    		g[p].push_back(i);
    		assert(dsu.merge(i - 1, p - 1));
    	}
    	else
    		r = i;
    }
    dfs(r);
    // for(int i = 1; i <= n; i++) {
    // 	for(int j = 1; j <= m; j++) 
    // 		cout << dp[i][j] << ' ';
    // 	cout << '\n';
    // }
    cout << dp[r][m] << '\n';
    return 0;
}

Compilation message (stderr)

biochips.cpp: In instantiation of 'disjoint_set<Enable_small_to_large>::disjoint_set(int) [with bool Enable_small_to_large = true]':
biochips.cpp:58:23:   required from here
biochips.cpp:25:17: warning: 'disjoint_set<true>::p' will be initialized after [-Wreorder]
   25 |     vector<int> p;
      |                 ^
biochips.cpp:24:12: warning:   'int disjoint_set<true>::cc' [-Wreorder]
   24 |     int n, cc;
      |            ^~
biochips.cpp:26:5: warning:   when initialized here [-Wreorder]
   26 |     disjoint_set(int n): n(n), p(n, -1), cc(n) { }
      |     ^~~~~~~~~~~~

• Subtask 1: 0 / 100