oj.uz

Submission #680012

# Submission time Handle Problem Language Result Execution time Memory
680012 2023-01-09T18:59:01 Z pragmatist Biochips (IZhO12_biochips) C++17
100 / 100
 517 ms 30836 KB 
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
*/

#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)2e5 + 7; // make sure this is right
const int M = (int)2e6 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, m, a[N], b[N], le[N], dp[N][2];
int timer, tin[N], tout[N];
vector<int> g[N];

void dfs(int v, int pr) {
	tin[v] = ++timer;
	b[tin[v]] = a[v];
	for(auto to : g[v]) {
		if(to == pr) continue;
		dfs(to, v);
	}
	tout[v] = timer;
}

struct Data {
	int l, r, x;
};

bool cmp(Data l, Data r) {
	return l.r < r.r;
}

void solve() {
	cin >> n >> m;
	int root;
	for(int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		if(x != 0) {
			g[x].pb(i);
			g[i].pb(x);                 
		} else {
			root = i;
		}
		cin >> a[i];
	}                         
	dfs(root, root);
	vector<Data> v;
	for(int i = 1; i <= n; ++i) {
		v.pb({tin[i], tout[i], a[i]});
	}
	sort(all(v), cmp);
	set<int> s;
	int o = 0;
	for(auto [l, r, e] : v) {
		auto it = s.lower_bound(l);
	    if(it != s.begin()) {
			it--;
			le[o] = *it;
		}
		o++;
		s.insert(r);
	}
	for(int t = 1; t <= m; ++t) {
		for(int i = 0; i < sz(v); ++i) {
			int r = v[i].r, j = le[i], e = v[i].x;
			if(t == 1) dp[r][1] = max(dp[r][1], e);
			if(j == 0) continue;
			dp[r][1] = max(dp[r][1], dp[j][0] + e);
			dp[r][1] = max(dp[r][1], dp[j][1]);
		}
		for(int i = 1; i <= n; ++i) {
			swap(dp[i][1], dp[i][0]);
			dp[i][1] = 0;
		}	
	}
	cout << dp[n][0];
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("d.in", "r", stdin);
	//freopen("d.out", "w", stdout); 
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Compilation message

biochips.cpp: In function 'void solve()':
biochips.cpp:79:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  dfs(root, root);
      |  ~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 9 ms 5908 KB Output is correct
5 Correct 10 ms 6124 KB Output is correct
6 Correct 13 ms 6128 KB Output is correct
7 Correct 295 ms 24788 KB Output is correct
8 Correct 290 ms 24776 KB Output is correct
9 Correct 396 ms 28488 KB Output is correct
10 Correct 517 ms 30836 KB Output is correct