Submission #1081740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081740		kiethm07	Harbingers (CEOI09_harbingers)	C++11	100 / 100	73 ms	23380 KiB

harbingers

#include <bits/stdc++.h>

#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define pb(i) push_back(i)
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 2e5 + 5;

struct line{
    ll a,b;
    line(){}
    line(ll _a, ll _b){
        a = _a;
        b = _b;
    }
    ll eval(ll x){
        return a * x + b;
    }
    ll isect(const line& F) const{
        return (F.b - b) / (a - F.a);
    }
};

vector<pii> a[N];
int n;
int dis[N];
ll s[N], v[N];
line hull[N];
ll dp[N];

int getAdd(line F,int r){
    int l = 1;
    int res = r + 1;
    while(l <= r){
        int mid = (l + r + 1) / 2;
        if (mid == 1) return 2;
        if (hull[mid].isect(hull[mid - 1]) <= F.isect(hull[mid])){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return res;
}

ll query(int x,int r){
    if (r == 0) return 0;
    if (r == 1) return hull[1].eval(x);
    int res = 1;
    int l = 1;
    while(l <= r){
        int mid = (l + r + 1) / 2;
        if (mid == 1) return hull[1].eval(x);
        if (hull[mid].eval(x) < hull[mid - 1].eval(x)){
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return hull[res].eval(x);
}

void print(int r){
    for (int i = 1; i <= r; i++){
        cout << i << "th: " << "a = " << hull[i].a << " --- " << "b = " << hull[i].b << "\n";
    }
    cout << "\n";
}

void dfs(int u,int p,int cur){
    //cout << u << " " << cur << " " << -v[u] << " " << query(-v[u],cur) << "\n";
    //print(cur);
    dp[u] = s[u] + dis[u] * v[u] + query(-v[u],cur);
    line F = line(dis[u],dp[u]);
    int posAdd = getAdd(F,cur);
    line preLine = hull[posAdd];
    hull[posAdd] = F;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        dis[v] = dis[u] + w;
        dfs(v,u,posAdd);
    }
    hull[posAdd] = preLine;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
        freopen(TEXT".out","w",stdout);
    }
    cin >> n;
    for (int i = 1; i < n; i++){
        int u,v,w;
        cin >> u >> v >> w;
        a[u].pb(pii(v,w));
        a[v].pb(pii(u,w));
    }
    for (int i = 2; i <= n; i++){
        cin >> s[i] >> v[i];
    }
    dfs(1,-1,0);
    for (int i = 2; i <= n; i++) cout << dp[i] << " ";
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int, int, int)':
harbingers.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100