Submission #1106419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106419		VKhang	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1065 ms	17272 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define fi first
#define se second
struct Line{
    long long m,b;
};
struct SAVE{
    int x;
    int y;
    Line z;
};
int n;
vector <pair <int,int>> s[N];
vector <SAVE> Save;
int a[N], b[N];
int d[N];
long long dp[N];
int Size = 0;
Line line[N];
bool bad(Line l1, Line l2, Line l3){
    return ((1ll * (l1.b - l2.b) * (l3.m - l1.m)) > (1ll * (l1.b - l3.b) * (l2.m - l1.m)));
}
long long calc(int x, int id){
    return 1ll * line[id].m * x + line[id].b;
}
void add_Line(long long m, long long b){
    int l = 1, r = Size;
    int id = Size + 1;
    Line newLine = {m, b};
//    while(l <= r){
//        int mid = (l + r)/2;
//        if (bad(line[mid - 1], line[mid], newLine)){
//            id = mid;
//            r = mid - 1;
//        }
//        else l = mid + 1;
//    }
    for (int i = Size; i >= 2; i--){
        if (bad(line[i - 1], line[i], newLine)){
            id = i;
        }
        else break;
    }

    Save.push_back({id, Size, line[id]});
    Size = id;
    line[id] = newLine;
}
long long Query(int x){
    int l = 1, r = Size;
    long long ans = 1e18;
//    while (l <= r){
//        int mid = (l + r)/2;
//        long long u = calc(x, mid);
//        long long v = calc(x, mid + 1);
//        if (u >= v) l = mid + 1;
//        else r = mid - 1;
//        ans = min({ans, u, v});
//    }
for (int i = 1; i <= Size; i++){
    ans = min(ans, calc(x, i));
}
    return ans;
}
void undo(){
    int id = Save.back().x;
    int re_size = Save.back().y;
    Line old_line = Save.back().z;
    line[id] = old_line;
    Size = re_size;
    Save.pop_back();
}
void dfs(int i, int pre){
    if (i != pre){
        dp[i] = a[i] + 1ll * d[i] * b[i] + Query(b[i]);
    }
    add_Line( -d[i], dp[i]);
    for (auto x: s[i]){
        if (x.fi == pre)
            continue;
        d[x.fi] = d[i] + x.se;
        dfs(x.fi, i);
    }
    undo();
}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i++){
        int u,v,w;
        cin >> u >> v >> w;
        s[u].push_back({v,w});
        s[v].push_back({u,w});
    }
    for (int i = 2; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    dfs(1, 1);
    for (int i = 2; i <= n; i++){
        cout << dp[i] << " ";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
  
    solve();
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void add_Line(long long int, long long int)':
harbingers.cpp:29:9: warning: unused variable 'l' [-Wunused-variable]
   29 |     int l = 1, r = Size;
      |         ^
harbingers.cpp:29:16: warning: unused variable 'r' [-Wunused-variable]
   29 |     int l = 1, r = Size;
      |                ^
harbingers.cpp: In function 'long long int Query(int)':
harbingers.cpp:52:9: warning: unused variable 'l' [-Wunused-variable]
   52 |     int l = 1, r = Size;
      |         ^
harbingers.cpp:52:16: warning: unused variable 'r' [-Wunused-variable]
   52 |     int l = 1, r = Size;
      |                ^

• Subtask 1: 70 / 100