Submission #648428

#	Time	Username	Problem	Language	Result	Execution time	Memory
648428		Moses	Harbingers (CEOI09_harbingers)	C++11	20 / 100	164 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define prl(x) printf("%lld\n",x)
#define yes printf("YES\n")
#define no printf ("NO\n")
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define s second
#define tmp (l+r)/2
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ld pi=2*acos(0);
const ll mod=1e9+7;
const ld eps=1e-9;
const ll ll_max=4e18;
///const ll mod=998244353;
 
/// make the equation y=m*x+p+g
/// where g is constant and y==dp[i]
/// dp[i]=query(x)+g;
/// Line l={m,p};
/// insert(node*,l);
/// if you want max
/// dp[i]=-query(x)+g;
/// Line l={-m,-p};
/// insert(node* ,l);
 
using namespace std;
ll RANG = 0;
ll RANGM = 2e9;
struct Line{
    int m;
    ll p;
    Line(){
        m=0;
        p=ll_max;
    }
}fai;
struct node{
    Line line;
    node *l;
    node *r;
    node(Line line2=fai,node *l2=NULL,node *r2=NULL)
    {
        line=line2;
        l=l2;
        r=r2;
    }
};
ll f(Line l,ll x){
    return l.m*x+l.p;
}
node* insert(node *cur,Line line,ll st=RANGM,ll en=RANG)
{
    node *ret=new node(cur->line,cur->l,cur->r);
    ll m=st+(en-st)/2ll;
    bool left = f(line, st) < f(ret->line, st);
    bool mid = f(line, m) < f(ret->line, m);
    if(mid)
        swap(line,ret->line);
    if(ret->l==NULL)
        ret->l=new node();
    if(ret->r==NULL)
        ret->r=new node();
 
    if(en - st == 0)
    {
        return ret;
    }
    else if(left != mid)
    {
        node *lef=insert(ret->l,line,st,m);
        ret->l=lef;
        return ret;
    }
    else
    {
        node *right=insert(ret->r,line,m+1,en);
        ret->r=right;
        return ret;
    }
}
ll query(node *cur,ll x,ll st=RANGM,ll en=RANG)
{
	if (cur == NULL) return f(fai,x);
    ll m = st+(en-st)/2ll;
    ll curr = f(cur->line, x);
    if(en-st==0) return curr;
 
    if(x<=m) return min(curr, query(cur->l,x, st, m));
    else return min(curr, query(cur->r,x, m+1, en));
}
int n;
ll s[100001];
ll v[100001];
vector<pair<int,ll>>vec[100001];
node *root[100001];
ll mem[100001];
void dfs(int city,int par,ll q)
{
    if(city!=1)
    {
        mem[city]=(query(root[par],v[city])+q*v[city])+s[city];
        root[city]=root[par];
        Line l;
        l.m=-q;
        l.p=mem[city];
        root[city]=insert(root[city],l);
    }
    for(auto c:vec[city])
    {
        if(c.f==par)
            continue;
        dfs(c.f,city,c.s+q);
    }
 
}
int main()
{
 
    sc(n);
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        ll c;
        sc(x);sc(y);scl(c);
        vec[x].pb({y,c});
        vec[y].pb({x,c});
    }
    for(int i=2;i<=n;i++)
    {
        scl(s[i]);
        scl(v[i]);
        RANG=max(RANG,v[i]);
        RANGM=min(RANGM,v[i]);
    }
    root[1]=new node();
    Line l;
    l.m=l.p=0;
    root[1]=insert(root[1],l);
    dfs(1,0,0);
    for(int i=2;i<=n;i++)
        printf("%lld ",mem[i]);
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define sc(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
harbingers.cpp:125:5: note: in expansion of macro 'sc'
  125 |     sc(n);
      |     ^~
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define sc(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
harbingers.cpp:130:9: note: in expansion of macro 'sc'
  130 |         sc(x);sc(y);scl(c);
      |         ^~
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define sc(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
harbingers.cpp:130:15: note: in expansion of macro 'sc'
  130 |         sc(x);sc(y);scl(c);
      |               ^~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define scl(x) scanf("%lld",&x)
      |                ~~~~~^~~~~~~~~~~
harbingers.cpp:130:21: note: in expansion of macro 'scl'
  130 |         sc(x);sc(y);scl(c);
      |                     ^~~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define scl(x) scanf("%lld",&x)
      |                ~~~~~^~~~~~~~~~~
harbingers.cpp:136:9: note: in expansion of macro 'scl'
  136 |         scl(s[i]);
      |         ^~~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define scl(x) scanf("%lld",&x)
      |                ~~~~~^~~~~~~~~~~
harbingers.cpp:137:9: note: in expansion of macro 'scl'
  137 |         scl(v[i]);
      |         ^~~

• Subtask 1: 20 / 100