제출 #1196745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196745		MuhammadSaram	Harbingers (CEOI09_harbingers)	C++20	70 / 100	259 ms	131072 KiB

harbingers

// Time: 06-05-2025 07:34:15
// Problem: A - Commando
// Contest: Virtual Judge - Contest 3
// URL: https://vjudge.net/contest/714915#problem/A
// Memory Limint: 32 MB
// Time Limint: 500 ms

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 1e5 + 1;

int ve[M],dep[M];
ll dp[M];
vector<pair<pair<int,ll>,int>> v,rem[M];
vector<pair<int,int>> nei[M];

pair<ll,int> poi(int m,ll c,int m1,ll c1)
{
	return {(c-c1),(m1-m)};
}

bool comp(pair<ll,int> p,pair<ll,int> p1)
{
	if (p.first/p.second>p1.first/p1.second)
		return 1;
	else if(p.first/p.second==p1.first/p1.second)
		return 1ll*p.first%p.second*p1.second>1ll*p1.first%p1.second*p.second;
	return 0;
}

void add(int m,ll c,int id)
{
	while (v.size()>1)
	{
		pair<int,ll> p={v[v.size()-2].first.first,v[v.size()-2].first.second},p1={v.back().first.first,v.back().first.second};
		if (comp(poi(p.first,p.second,m,c),poi(p.first,p.second,p1.first,p1.second)))
			rem[id].push_back(v.back()),v.pop_back();
		else
			break;
	}
	// rem[id].shrink_to_fit();
	v.push_back({{m,c},id});
}

ll get(int x)
{
	ll ans=1ll*v[0].first.first*x+v[0].first.second;
	int s=0,e=v.size();
	while (s+1<e)
	{
		int mid=(s+e)/2;
		ll val=1ll*v[mid-1].first.first*x+v[mid-1].first.second;
		ll val1=1ll*v[mid].first.first*x+v[mid].first.second;
		if (val<val1)
			ans=max(ans,val1),s=mid;
		else
			ans=max(ans,val),e=mid;
	}
	return ans;
}

void dfs(int u,int p=0)
{
	if (!p)
		add(0,0,1);
	else
	{
		dp[u]+=-get(-ve[u])+1ll*dep[u]*ve[u];
		add(-dep[u],-dp[u],u);
	}
	while (!nei[u].empty())
	{
		int i=nei[u].back().first,d=nei[u].back().second;
		nei[u].pop_back();
		if (i!=p)
			dep[i]=dep[u]+d,dfs(i,u);
	}
	nei[u].shrink_to_fit();
	v.pop_back();
	while (!rem[u].empty())
	{
		auto i=rem[u].back();rem[u].pop_back();
		add(i.first.first,i.first.second,i.second);
	}
	// rem[u].shrink_to_fit();
}

signed main()
{
	// ios::sync_with_stdio(0);
	// cin.tie(NULL), cout.tie(NULL);
	int n;
	cin>>n;
	v.reserve(n);
	for (int i=1;i<n;i++)
	{
		int u,v,d;
		scanf("%d%d%d",&u,&v,&d);
		// cin>>u>>v>>d;
		nei[u].push_back({v,d});
		nei[v].push_back({u,d});
	}
	for (int i=2;i<=n;i++)
		scanf("%lld%d",&dp[i],&ve[i]),nei[i].shrink_to_fit();
	dfs(1);
	for (int i=2;i<=n;i++)
		printf("%lld ",dp[i]);
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp: In function 'int main()':
harbingers.cpp:102:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 scanf("%d%d%d",&u,&v,&d);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:108:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                 scanf("%lld%d",&dp[i],&ve[i]),nei[i].shrink_to_fit();
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100