제출 #1171691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171691		PedroBigMan	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	407 ms	589824 KiB

worst_reporter2

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll M; ll N; vector<ll> r,c;

class Tree
{
    public:
    ll N; 
    vector<ll> p; 
    vector<vector<ll> > sons;
    vector<vector<ll> > adj;
    ll root;
    vector<bool> visited;
	vector<vector<ll> > dp;
    
    Tree(vector<vector<ll> > ad, ll r=0LL)
    {
        N=ad.size(); root=r; adj=ad;
        REP(i,0,N) {visited.pb(false);}
        vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);}
        DFS_Build(r,r);
		REP(i,0,M) {xx.pb(-1LL);}
		REP(i,0,N) {dp.pb(xx);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS_Build(ll s, ll par)
    {
        p[s]=par;
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(adj[s][i]==par) {continue;}
            sons[s].pb(adj[s][i]);
            DFS_Build(adj[s][i],s);
        }
        return;
    }
	
	void DP(ll s)
	{
		if(dp[s][0]!=-1) {return;}
		REP(i,0,sons[s].size()) 
		{
			ll son=sons[s][i]; DP(son);
		}
		if(sons[s].size()==0) 
		{
			REP(i,0,M) {dp[s][i]=c[s];} 
			dp[s][r[s]]=0LL;
			return;
		}
		ll S = sons[s].size(); ll son; ll sum=0LL;
		vector<ll> bestyet; REP(i,0,S) {son=sons[s][i]; bestyet.pb(dp[son][M-1]); sum+=dp[son][M-1];}
		dp[s][M-1] = c[s]+sum;
		for(ll val=M-2;val>=0;val--)
		{
			REP(i,0,S) 
			{
				son=sons[s][i]; 
				if(dp[son][val]<bestyet[i]) 
				{
					sum-=(bestyet[i]-dp[son][val]);
					bestyet[i]=dp[son][val];
				}
			}
			dp[s][val]=c[s]+sum;
		}
		dp[s][r[s]]-=c[s];
		return ;
	}
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>N; vector<ll> xx; vector<vector<ll> > adj; REP(i,0,N) {adj.pb(xx);}
	ll cur;
	ll rat, cost;
	REP(i,0,N) 
	{
		cin>>cur>>rat>>cost; r.pb(rat); c.pb(cost); if(i==0) {continue;}
		cur--; adj[cur].pb(i); adj[i].pb(cur);
	}
	set<ll> s; REP(i,0,N) {s.insert(r[i]);}
	set<ll>::iterator it=s.begin();
	unordered_map<ll,ll> comp; cur=0LL;
	while(it!=s.end())
	{
		comp[*it]=cur; cur++;
		it++;
	}
	M = s.size();
	Tree T(adj);
	REP(i,0,N) {r[i]=comp[r[i]];}
	T.DP(0LL);
	cout<<*min_element(whole(T.dp[0]))<<endl;
    return 0;
}

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