Submission #933948

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
933948	2024-02-26T15:28:03 Z	mraron	Harbingers (CEOI09_harbingers)	C++14	0 / 100	1000 ms	17364 KB

harbingers

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#define ins insert
#define chkmn(x,y) (x)=min((x), (y))
#define chkmx(x,y) (x)=max((x), (y))

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

using ll = long long;
using ull = unsigned long long ;
using ld = long double ;
using str = string;
//using ordered_set=tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
    T val=0;
    char c;
    
    bool neg=false;
    while((c=gc()) && !(c>='0' && c<='9')) {
        neg|=c=='-';
    }

    do {
        val=(val*10)+c-'0';
    } while((c=gc()) && (c>='0' && c<='9'));

    return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


struct line {
    ll m,b;
    ll at(ll x) const {
        return m*x+b;
    }
};

struct magic_stack {
    int sz=0;
    vector<line> lst;
    
    magic_stack() {
        lst.resize(100501);
    }
    
    bool inter(line x, line y, line z) {
        return (x.b-y.b)*(-y.m+z.m)>=(y.b-z.b)*(-x.m+y.m);
    }
    
    pair<int, line> add(line l) {
        if(sz<=1) {
            int prev_sz=sz;
            auto tmp=lst[sz];
            lst[sz++]=l;
            return {prev_sz, tmp};
        } 
        int x=sz(lst)-2;
        while(x>=0 && inter(lst[x],lst[x+1],l)) {
            x--;
        }
        int prev_sz=sz;
        auto tmp=lst[x+2];
        lst[x+2]=l;
        sz=x+3;
        return {prev_sz, tmp};
    }
    
    ll get(ll x) {
        int L=0, R=sz-1;
        while(L<R) {
            int mid=(L+R)/2;
            if(lst[mid].at(x)<lst[mid+1].at(x)) {
                R=mid;
            }else {
                L=mid+1;
            }
        }
        return lst[L].at(x);
    }
    
    
    
    void debug() {
        for(auto i:lst) cerr<<i.m<<" "<<i.b<<"\n";
    }
};

vector<pair<int,ll>> adj[100001];
ll s[100001], v[100001], ans[100001];
int st[100010];
pair<int, line> todo[100010];
void dfs(int x, magic_stack& ms, ll depth=0) {
    st[x]=1;
    if(x>1) {
        ans[x]=depth*v[x]+s[x];
        if(ms.lst.size()>0) {
            ans[x]=min(ans[x], ms.get(v[x])+s[x]+depth*v[x]);
        }
        todo[x]=ms.add(line{-depth, ans[x]});
    }

    for(auto i:adj[x]) {
        if(!st[i.xx]) {
            dfs(i.xx, ms, depth+i.yy);
        }
    }
    
    if(x>1) {
        ms.lst[ms.sz-1]=todo[x].yy;
        ms.sz=todo[x].xx;
    }
}

int main() {
    IO;
    //bazd meg ojuz
    //freopen("harbingers.in", "r", stdin);
    //freopen("harbingers.out", "w", stdout);
    int n;
    cin>>n;
    for(int i=0;i<n-1;++i) {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    for(int i=2;i<=n;++i) {
        cin>>s[i]>>v[i];
    }
    
    magic_stack ms;
    dfs(1, ms);
    for(int i=2;i<=n;++i) cout<<ans[i]<<" \n"[i==n];
    
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	7004 KB	Output isn't correct
2	Incorrect	341 ms	7664 KB	Output isn't correct
3	Execution timed out	1047 ms	14064 KB	Time limit exceeded
4	Execution timed out	1034 ms	14812 KB	Time limit exceeded
5	Execution timed out	1026 ms	15884 KB	Time limit exceeded
6	Execution timed out	1040 ms	17364 KB	Time limit exceeded
7	Execution timed out	1022 ms	15080 KB	Time limit exceeded
8	Execution timed out	1053 ms	17340 KB	Time limit exceeded
9	Execution timed out	1063 ms	17288 KB	Time limit exceeded
10	Execution timed out	1059 ms	16644 KB	Time limit exceeded