제출 #445207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445207		mosiashvililuka	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	14 / 100	244 ms	201684 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std;
int A[200009],H[200009],C[200009];
int a,b,c,d,e,i,j,ii,jj,zx,xc;
long long dp[5003][5003];
//pair <pair <int, int>, int> p[200009];
vector <int> v[200009];
void dfs(int q, int w){
	for(j=1; j<=5000; j++){
		if(j!=H[q]) dp[q][j]+=C[q];
	}
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
		for(j=1; j<=5000; j++){
			dp[q][j]+=dp[(*it)][j];
		}
	}
	for(j=4999; j>=1; j--){
		dp[q][j]=min(dp[q][j+1],dp[q][j]);
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	map <int, int> mp;
	map <int, int>::iterator it;
	cin>>a;
	for(i=1; i<=a; i++){
		//cin>>p[i].first.first>>p[i].first.second>>p[i].second;
		cin>>A[i]>>H[i]>>C[i];
		mp[H[i]]++;
	}
	zx=0;
	for(it=mp.begin(); it!=mp.end(); it++){
		zx++;
		(*it).second=zx;
	}
	for(i=1; i<=a; i++){
		H[i]=mp[H[i]];
	}
	for(i=2; i<=a; i++){
		v[A[i]].push_back(i);
	}
	dfs(1,0);
	cout<<dp[1][1];
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21