oj.uz

Submission #641316

# Submission time Handle Problem Language Result Execution time Memory
641316 2022-09-16T11:48:08 Z sumit_kk10 Harbingers (CEOI09_harbingers) C++17
0 / 100
 102 ms 23072 KB 
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;
vector<pair<int, int> > g[N];
int n, par[N], dis[N], dp[N], s[N], d[N];
bool vis[N];
 
struct Line{
    int m, c;
 
    int val(int x){
        return m*x + c;
    }
};
 
deque<pair<Line, int> > hulls;
 
bool check(Line a, Line b, Line cc){
    int x = (b.c - a.c);
    x = x * (a.m - cc.m);
    int y = (cc.c - a.c);
    y = y * (a.m - b.m);
    if(x > y)
        return true;
    return false;
}
 
void insert(int mm, int cc, int node){
    Line cur;
    cur.m = mm;
    cur.c = cc;
    if(!hulls.empty() and hulls[0].F.m == mm){
        if(hulls[0].F.c > cc){
            vis[hulls[0].S] = false;
            hulls.pop_front();
        }
        else{
            vis[node] = false;
            return;
        }
    }
    while(hulls.size() > 1){
        if(check(hulls[1].F, hulls[0].F, cur)){
            vis[hulls[0].S] = false;
            hulls.pop_front();
        }
        else
            break;
    }
    hulls.push_front({cur, node});
}
 
int get(int x){
    if(hulls.empty())
        return 1e15;
    int low = 0, high = (int) hulls.size() - 2, ans = (int) hulls.size() - 1;
    while(low <= high){
        int mid = (low + high) / 2;
        if(hulls[mid].F.val(x) <= hulls[mid + 1].F.val(x)){
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return hulls[ans].F.val(x);
}
 
void dfs(int node, int p, int sum){
    dis[node] = sum;
    par[node] = p;
    for(auto k : g[node]){
        if(k.F == p) continue;
        dfs(k.F, node, sum + k.S);
    }
}
 
void dfs1(int node){
    int mn = s[node] + dis[node] * d[node];
    mn = min(mn, get(-d[node]) + s[node] + dis[node] * d[node]);
    dp[node] = mn;
    for(auto k : g[node]){
        if(k.F == par[node]) continue;
        if(node != 1 and !vis[node]){
            vis[node] = true;
            insert(dis[node], dp[node], node);
        }
        dfs1(k.F);
    }
    if(vis[node])
        hulls.pop_front();
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].pb({v, c});
        g[v].pb({u, c});
    }
    for(int i = 1; i < n; ++i)
        cin >> s[i + 1] >> d[i + 1];
    dfs(1, 0, 0);
    dfs1(1);
    for(int i = 2; i <= n; ++i)
        cout << dp[i] << " ";
}
 
int32_t main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Incorrect 4 ms 3152 KB Output isn't correct
3 Incorrect 42 ms 11520 KB Output isn't correct
4 Incorrect 56 ms 15256 KB Output isn't correct
5 Incorrect 80 ms 19532 KB Output isn't correct
6 Incorrect 102 ms 23072 KB Output isn't correct
7 Incorrect 50 ms 13388 KB Output isn't correct
8 Incorrect 100 ms 18804 KB Output isn't correct
9 Incorrect 99 ms 19952 KB Output isn't correct
10 Incorrect 76 ms 18680 KB Output isn't correct