oj.uz

Submission #346415

# Submission time Handle Problem Language Result Execution time Memory
346415 2021-01-09T15:27:47 Z LeMans Biochips (IZhO12_biochips) C++17
100 / 100
 784 ms 390508 KB 
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;

typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;

#define F first
#define S second

#define en end()
#define bg begin()

#define rev reverse
#define mp make_pair
#define pb push_back

#define y1 y1234567890
#define um unordered_map

#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)

#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))

#define forn(i, n) for (int i = 1; i <= n; i++)

const int inf = (int)1e9;
const ll mod = (ll)1e9 + 7;

const db eps = (db)1e-9;
const db pi = acos(-1.0);

const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

const int N = 200500;
const int M = 505;

int timer, tin[N], tout[N], eu[N];
int n, m, root, a[N], dp[M][N];
vector < int > g[N];

void dfs(int v) {
	tin[v] = ++timer;
	eu[timer] = v;
	for (auto to : g[v])
		dfs(to);
	tout[v] = timer;
}

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	//freopen(".err", "w", stderr);

	//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

	//cin.tie(NULL);
	//cout.tie(NULL);
	//ios_base::sync_with_stdio(false);

	//cout << setprecision(10) << fixed;
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int p;
		scanf("%d %d", &p, &a[i]);
		if (p) g[p].pb(i);
		else root = i;
		for (int j = 1; j <= m; j++)
			dp[j][i] = -inf;
	}
	for (int j = 1; j <= m; j++)
		dp[j][n + 1] = -inf;
	dfs(root);
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++)
			dp[j][i] = dp[j][i + 1];
		int v = eu[i];
		if (tout[v] == n) {
			dp[1][i] = max(dp[1][i], a[v]);
			continue;
		}
		int pr = tout[v] + 1;
		for (int j = 1; j <= m; j++) {
			if (dp[j - 1][pr] != -inf)
				dp[j][i] = max(dp[j][i], dp[j - 1][pr] + a[v]);
		}
	}
	printf("%d", dp[m][1]);

	//cerr << (clock() + 0.0) / CLOCKS_PER_SEC;

	return 0;
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |   scanf("%d %d", &p, &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 10 ms 7788 KB Output is correct
5 Correct 12 ms 8832 KB Output is correct
6 Correct 13 ms 9836 KB Output is correct
7 Correct 348 ms 184556 KB Output is correct
8 Correct 344 ms 184428 KB Output is correct
9 Correct 516 ms 286700 KB Output is correct
10 Correct 784 ms 390508 KB Output is correct