Submission #478059

#	Time	Username	Problem	Language	Result	Execution time	Memory
478059		clifter	Harbingers (CEOI09_harbingers)	C++14	100 / 100	280 ms	24024 KiB

harbingers

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

struct triple{ll x, a, b;};

vector<ll> V[100500],D[105000];
vector<triple> S;
priority_queue<pair<ll, int>> pq;
ll a[100500], b[100500], xsum[100500];
ll ans[100500];

void dfs(int x){
  for(int i=0; i<V[x].size(); i++){
    if(xsum[V[x][i]]==0&&V[x][i]!=1){
      xsum[V[x][i]] = xsum[x]+D[x][i];
      dfs(V[x][i]);
    }
  }
}

int main() {
  
  int n;
  cin>>n;
  for(int i=1; i<n; i++){

    int x,y,d;
    cin>>x>>y>>d;
    V[x].push_back(y);
    V[y].push_back(x);
    D[x].push_back(d);
    D[y].push_back(d);

  }

  for(int i=2; i<=n; i++) cin>>a[i]>>b[i];
  dfs(1);

  pq.push(make_pair(0, 1));

  while(!pq.empty()){

    ll val = pq.top().first;
    int node = pq.top().second;

    pq.pop();
    while(!S.empty()&&S.back().x>=val) S.pop_back();

    S.push_back(triple{val, -xsum[node], ans[node]});

    for(int i=0; i<V[node].size(); i++){

      if(ans[V[node][i]]==0&&V[node][i]!=1){

        int s = 0;
        int e = S.size()-1;
        while(s!=e){

          int m = (s+e)/2+1;
          if(S[m].x<=b[V[node][i]]) s = m;
          else e = m-1;

        }

        ans[V[node][i]] = a[V[node][i]]+b[V[node][i]]*(xsum[V[node][i]]+S[s].a)+S[s].b;
        
        s = 0;
        e = S.size()-1;
        while(s!=e){

          int m = (s+e)/2+1;
          if(S[m].a*S[m].x+S[m].b<-xsum[V[node][i]]*S[m].x+ans[V[node][i]]) s = m;
          else e = m-1;

        }

        ll x = (ans[V[node][i]]-S[s].b)/(xsum[V[node][i]]+S[s].a);
        pq.push(make_pair(x+1, V[node][i]));   

      }

    }
  }

  for(int i=2; i<=n; i++) cout<<ans[i]<<" ";

}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int)':
harbingers.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int i=0; i<V[x].size(); i++){
      |                ~^~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0; i<V[node].size(); i++){
      |                  ~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100