Submission #646562

#	Time	Username	Problem	Language	Result	Execution time	Memory
646562		arthur	Harbingers (CEOI09_harbingers)	C++14	20 / 100	149 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=2e18;
///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;
const ll RANG = 2e9;
struct Line{
    ll m,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=-RANG,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 *left=insert(ret->l,line,st,m);
        ret->l=left;
        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=-RANG,ll en=RANG)
{
    ll m = st+(en-st)/2ll;
    ll curr = f(cur->line, x);
    if(en-st==0) return curr;
    if(cur->l==NULL)
        cur->l=new node();
    if(cur->r==NULL)
        cur->r=new node();

    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[200200];
ll v[200200];
vector<pair<int,ll>>vec[200200];
node *root[200200];
ll dist[200200];
ll mem[200200];
void dfs(int city,int par,ll q)
{
    if(city!=1)
    {
        dist[city]=dist[par]+q;
        mem[city]=query(root[par],v[city])+s[city]+dist[city]*v[city];
        root[city]=root[par];
        Line l;
        l.m=-dist[city];
        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);
    }

}
int main()
{
    root[1]=new node();
    Line l;
    l.m=l.p=0;
    root[1]=insert(root[1],l);
    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]);
    }
    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:131:5: note: in expansion of macro 'sc'
  131 |     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:136:9: note: in expansion of macro 'sc'
  136 |         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:136:15: note: in expansion of macro 'sc'
  136 |         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:21: note: in expansion of macro 'scl'
  136 |         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:142:9: note: in expansion of macro 'scl'
  142 |         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:143:9: note: in expansion of macro 'scl'
  143 |         scl(v[i]);
      |         ^~~

• Subtask 1: 20 / 100