oj.uz

Submission #870705

# Submission time Handle Problem Language Result Execution time Memory
870705 2023-11-09T01:00:04 Z Saul0906 Harbingers (CEOI09_harbingers) C++14
0 / 100
 45 ms 65536 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65536 KB Execution killed with signal 9
2 Runtime error 45 ms 65536 KB Execution killed with signal 9
3 Runtime error 26 ms 65536 KB Execution killed with signal 9
4 Runtime error 29 ms 65536 KB Execution killed with signal 9
5 Runtime error 27 ms 65536 KB Execution killed with signal 9
6 Runtime error 27 ms 65536 KB Execution killed with signal 9
7 Runtime error 27 ms 65536 KB Execution killed with signal 9
8 Runtime error 28 ms 65536 KB Execution killed with signal 9
9 Runtime error 27 ms 65536 KB Execution killed with signal 9
10 Runtime error 28 ms 65536 KB Execution killed with signal 9