Submission #1263089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263089		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	0 / 100	1 ms	2632 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<pair<int, long long>> adj[MAXN];
long long dist[MAXN];  // distance from capital
long long S[MAXN], V[MAXN];  // startup time and speed for each harbinger
long long dp[MAXN];  // minimum time from each town to capital
int n;

struct Line {
    long long x, y;  // point (x, y) where x = dist, y = dp
};

vector<Line> hull;  // convex hull for current path

// Check if line j is redundant given lines i and k
bool bad(const Line& i, const Line& j, const Line& k) {
    // Using 128-bit integers to avoid overflow
    return (__int128)(j.y - i.y) * (k.x - i.x) >= (__int128)(k.y - i.y) * (j.x - i.x);
}

// Binary search for optimal line with given slope
long long query(long long slope) {
    if (hull.empty()) return 0;
    
    int l = 0, r = hull.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        long long val1 = hull[mid].y - slope * hull[mid].x;
        long long val2 = hull[mid + 1].y - slope * hull[mid + 1].x;
        if (val1 <= val2) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return hull[l].y - slope * hull[l].x;
}

void dfs(int u, int p) {
    // Save hull state for backtracking
    int prev_size = hull.size();
    
    if (u == 1) {
        dp[u] = 0;
    } else {
        // dp[u] = S[u] + V[u] * dist[u] + min over ancestors v of (dp[v] - V[u] * dist[v])
        dp[u] = S[u] + V[u] * dist[u] + query(V[u]);
    }
    
    // Add current node to hull
    Line new_line = {dist[u], dp[u]};
    
    // Remove redundant lines from hull
    while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull[hull.size() - 1], new_line)) {
        hull.pop_back();
    }
    hull.push_back(new_line);
    
    // Process children
    for (auto [v, w] : adj[u]) {
        if (v != p) {
            dist[v] = dist[u] + w;
            dfs(v, u);
        }
    }
    
    // Restore hull (backtrack)
    hull.resize(prev_size);
}

int main() {
    freopen("harbingers.in", "r", stdin);
    freopen("harbingers.out", "w", stdout);
    
    scanf("%d", &n);
    
    // Read edges
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long long d;
        scanf("%d %d %lld", &u, &v, &d);
        adj[u].push_back({v, d});
        adj[v].push_back({u, d});
    }
    
    // Read harbinger characteristics
    for (int i = 2; i <= n; i++) {
        scanf("%lld %lld", &S[i], &V[i]);
    }
    
    // Run DFS from capital
    dist[1] = 0;
    dfs(1, 0);
    
    // Output results
    for (int i = 2; i <= n; i++) {
        printf("%lld", dp[i]);
        if (i < n) printf(" ");
    }
    printf("\n");
    
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen("harbingers.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     freopen("harbingers.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
harbingers.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d %d %lld", &u, &v, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         scanf("%lld %lld", &S[i], &V[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100