Submission #564714

#	Time	Username	Problem	Language	Result	Execution time	Memory
564714		Karliver	Magic Tree (CEOI19_magictree)	C++17	0 / 100	50 ms	7584 KiB

magictree

#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, -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) {
		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
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17