oj.uz

Submission #871140

# Submission time Handle Problem Language Result Execution time Memory
871140 2023-11-10T03:08:38 Z Saul0906 Harbingers (CEOI09_harbingers) C++14
70 / 100
 187 ms 65536 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii 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<pii> ady[lim];
bool vis[lim]{};
pii harb[lim];
ll dp[lim]{};
ll dis=0;

struct line{
	ll m, b;
};

ll eval(line a, ll x){
	return (dis+a.m)*x+a.b;
}

ld isec(line l1, line l2){
	return (ld)(l1.b-l2.b)/(l2.m-l1.m);
}

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

ll solve(int u){
	ll l=0, r=cht.size()-1, mid, x=(ll)harb[u].se;
	while(l<=r){
		mid=(l+r)/2;
		if(mid==cht.size()-1 || isec(cht[mid],cht[mid+1])>=(ld)x) r=mid-1;
		else l=mid+1;
	}
	return eval(cht[l],x)+(ll)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 && isec(cht[sz-1],cht[sz-2])<=isec(cht[sz-1],cht[sz-3])){
		//cout<<isec(cht[sz-1],cht[sz-2])<<endl;
		deleted[u].push_back(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].back());
		deleted[u].pop_back();
	}
}

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;
}

Compilation message

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

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 4 ms 7772 KB Output is correct
3 Correct 63 ms 14776 KB Output is correct
4 Correct 82 ms 18256 KB Output is correct
5 Correct 120 ms 21844 KB Output is correct
6 Correct 147 ms 25264 KB Output is correct
7 Correct 86 ms 15700 KB Output is correct
8 Runtime error 187 ms 65536 KB Execution killed with signal 9
9 Runtime error 177 ms 65536 KB Execution killed with signal 9
10 Runtime error 176 ms 65536 KB Execution killed with signal 9