제출 #870705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870705		Saul0906	Harbingers (CEOI09_harbingers)	C++14	0 / 100	45 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
#define fi first
#define se second
#define pll pair<ll, ll>
#define ll long long
#define ld long double
#define rep(a,b,c) for(int a=b; a<c; a++) 
#define repa(a,b) for(auto a: b)

using namespace std;

const int lim=1e5+5;
vector<pll> ady[lim];
bool vis[lim]{};
pll harb[lim];
ll dp[lim]{};
ll dis=0;

struct line{
	ll m, b;
	ll eval(ll x){
		return (dis+m)*x+b;
	}
	ld isec(line a){
		return (b-a.b)/(a.m-m);
	}
};

deque<line> cht;
stack<line> deleted[lim];

ll solve(int u){
	ll l=0, r=cht.size()-1, mid, x=harb[u].se;
	while(l<=r){
		mid=(l+r)/2;
		if(mid==cht.size()-1 || cht[mid].isec(cht[mid+1])>=x) r=mid-1;
		else l=mid+1;
	}
	return cht[l].eval(x)+harb[u].fi;
}

void dfs(int u){
	vis[u]=true;
	if(u>1) dp[u]=solve(u);
	cht.push_back({-dis,dp[u]});
	int sz=cht.size();
	while(sz>2 && cht[sz-1].isec(cht[sz-2])<=cht[sz-1].isec(cht[sz-3])){
		deleted[u].push(cht[sz-2]);
		cht[sz-2]=cht[sz-1];
		cht.pop_back();
		sz--;
	}
	repa(v, ady[u]){
		if(!vis[v.fi]){
			dis+=v.se;
			dfs(v.fi);
			dis-=v.se;
		}
	}
	cht.pop_back();
	while(deleted[u].size()){
		cht.push_back(deleted[u].top());
		deleted[u].pop();
	}
}

int main(){
	ll u, v, w;
	int n;
	cin>>n;
	rep(i,1,n){
		cin>>u>>v>>w;
		ady[u].push_back({v,w});
		ady[v].push_back({u,w});
	}
	rep(i,2,n+1) cin>>harb[i].fi>>harb[i].se;
	dfs(1);
	rep(i,2,n+1) cout<<dp[i]<<" ";
	cout<<endl;
}

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

harbingers.cpp: In function 'long long int solve(int)':
harbingers.cpp:36:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if(mid==cht.size()-1 || cht[mid].isec(cht[mid+1])>=x) r=mid-1;
      |      ~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 100