oj.uz

Submission #871139

# Submission time Handle Problem Language Result Execution time Memory
871139 2023-11-10T03:03:44 Z Saul0906 Harbingers (CEOI09_harbingers) C++14
40 / 100
 196 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 (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])){
		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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 61 ms 15456 KB Output is correct
4 Incorrect 83 ms 19028 KB Output isn't correct
5 Correct 113 ms 23012 KB Output is correct
6 Incorrect 138 ms 26192 KB Output isn't correct
7 Incorrect 85 ms 17288 KB Output isn't correct
8 Runtime error 196 ms 65536 KB Execution killed with signal 9
9 Runtime error 183 ms 65536 KB Execution killed with signal 9
10 Runtime error 184 ms 65536 KB Execution killed with signal 9