oj.uz

Submission #564718

# Submission time Handle Problem Language Result Execution time Memory
564718 2022-05-19T13:57:57 Z Karliver Magic Tree (CEOI19_magictree) C++17
11 / 100
 63 ms 8908 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)


long long dp[N][21];
bool on[N];
int n, m, k;
int D[N], V[N], W[N];
vector<int> g[N];
long long  dfs(int v, int lm) {
	if(dp[v][lm] != -1)
		return dp[v][lm];
	
	long long &ret = dp[v][lm];
	ret = 0;
	for(auto c : g[v]) {
		long long ps = 0;
		if(on[c] && lm >= D[c])
			ps = max(ps, dfs(c, D[c]) + W[c]);
		ps = max(ps, dfs(c, lm));
		ret += ps;
		
	}
	
	return ret;
}
const int INF = 1e9 + 2;
void test_case() {
	
	
	
	cin >> n >> m >> k;
	
	
	
	
	for(int  j = 1;j < n;++j) {
		int x;
		cin >> x;
		--x;
		g[x].push_back(j);
	}
	
	for(int i = 0;i < m;++i) {
		int v, d, w;
		cin >> v >> d >> w;
		--v;
		on[v] = 1;
		D[v] = d;
		W[v] = w;
	}
	
	int res = 0;
	
	vector<int> p(n + 1, -INF);
	
	auto find_id = [&](int x) {
		int l = 0, r =n;
		
		while(l < r) {
			int md = (l + r) >> 1;
			if(x <= p[md]) l = md + 1;
			else r = md;
		}
		return l;
	};
	
	for(int j = 0;j < n;++j) {
		if(!on[j])continue;
		int ls = find_id(D[j]);
		res = max(res, ls + 1);
		p[ls] = D[j];
	}
	cout << res << '\n';
	
	
}
					
		

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tt;
	tt = 1;
	//cin >> tt;
	
	for(int p = 1;p <= tt;++p) {
		//cout << "Case #" << p << ": ";
		test_case();
	}
	
		
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 5284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 3 ms 2696 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 49 ms 8892 KB Output is correct
5 Correct 63 ms 8892 KB Output is correct
6 Correct 53 ms 8908 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 5512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -