Submission #934239

#	Time	Username	Problem	Language	Result	Execution time	Memory
934239		tamir1	Magic Tree (CEOI19_magictree)	C++14	49 / 100	764 ms	795036 KiB

magictree

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,p[100005],i,u,w,d,sum,c;
vector<ll> v[100005],de;
pair<ll,ll> fruit[100005];
vector<vector<ll>> a;
map<ll,ll> mp;
map<ll,ll> ::iterator it;
multiset<ll> s;
multiset<ll> ::iterator is;
bool ar;
void dfs(ll x){
	ll d=fruit[x].first;
	ll w=fruit[x].second;
	d=mp[d];
	a[x][d]=w;
	for(int i:v[x]){
		dfs(i);
		for(int j=1;j<=k;j++){
			a[x][j]+=a[i][j];
		}
	}
	for(int i=2;i<=k;i++) a[x][i]=max(a[x][i-1],a[x][i]);
}
int main(){
	cin >> n >> m >> k;
	ar=true;
	for(i=2;i<=n;i++){
		cin >> p[i];
		if(i-1!=p[i]) ar=false;
		v[p[i]].push_back(i);
	}
	for(i=1;i<=m;i++){
		cin >> u >> d >> w;
		mp[d]=1;
		fruit[u]={d,w};
		sum+=w;
		c++;
		de.push_back(d);
	}
	if(ar==true){
		reverse(de.begin(),de.end());
		for(i=0;i<de.size();i++){
			is=s.upper_bound(de[i]);
			if(is!=s.end()) s.erase(is);
			s.insert(de[i]);
		}
		cout << s.size();
		return 0;
	}
	k=0;
	for(it=mp.begin();it!=mp.end();it++){
		k++;
		mp[it->first]=k;
	}
	if(k>1000){
		cout << sum;
		return 0;
	}
	a=vector<vector<ll>> (n+1,vector<ll> (k+1,0));
	dfs(1);
	cout << a[1][k];
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:44:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(i=0;i<de.size();i++){
      |           ~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17