Submission #197305

#	Time	Username	Problem	Language	Result	Execution time	Memory
197305		quocnguyen1012	Harbingers (CEOI09_harbingers)	C++14	60 / 100	292 ms	47052 KiB

harbingers

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define taskname "HARBINGERS"

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;
vector<ii> adj[maxn];
ii a[maxn];
ll f[maxn];
int p[maxn];
ll dep[maxn];
int n;
int nTime = 0 , in[maxn] , out[maxn];
struct point{
    ll x , y;
    point(){};
    point(ll x , ll y):x(x),y(y){};
    point operator - (const point & other){
        return point(x - other.x , y - other.y);
    }
    ll operator * (const point & other){
        return x * other.y - y * other.x;
    }
    ll Val(int k){
        return x * k + y;
    }
};
bool ccw(point a , point b , point c){
    return (a - b) * (c - b) <= 0;
}
struct convex{
    vector<point> p;
    void add(point now){
        if(p.size() && now.x == p.back().x && now.y > p.back().y){
            return;
        }
        while(p.size() >= 2 && ccw(p[p.size() - 2],p[p.size() - 1],now))
            p.pop_back();
        p.pb(now);
    }
    ll query(int x){
        if(p.size() == 0)return 1e18;
        int l = 0 , h = p.size() - 1;
        while(l <= h){
            int mid = l + h >> 1;
            if(mid + 1 < p.size() && p[mid].Val(x) >= p[mid + 1].Val(x)){
                l = mid + 1;
            }else{
                h = mid - 1;
            }
        }
        return p[l].Val(x);
    }
}s[maxn * 4];

void dfs1(int u , int par){
    in[u] = ++nTime;
    for(auto c : adj[u]){
        if(c.first != par){
            dfs1(c.first , u);
        }
    }
    out[u] = nTime;
}

void update(int x , int l , int r , int L , int R , point now){
    if(L > r || l > R)return;
    if(L <= l && r <= R){
        s[x].add(now);
        return;
    }
    int mid = l + r >> 1;
    update(x * 2 , l , mid , L , R , now);
    update(x * 2 + 1 , mid + 1 , r , L , R , now);
}
ll query(int x , int l , int r , int pos , int k){
    if(l == r)return s[x].query(k);
    int mid = l + r >> 1;
    if(mid >= pos)return min(s[x].query(k),query(x*2,l,mid,pos,k));
    return min(s[x].query(k),query(x*2+1,mid+1,r,pos,k));
}
void dfs(int u,int par){
    f[u] = 1e18;
    if(u == 1)f[u] = 0;
    else{
        f[u] = query(1,1,n,in[u],a[u].second) + a[u].first + dep[u] * a[u].second;
    }
    update(1,1,n,in[u],out[u],point(-dep[u],f[u]));
    for(ii c : adj[u]){
        if(c.first == par)continue;
        dep[c.first] = dep[u] + c.second;
        dfs(c.first , u);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".IN","r")){
        freopen(taskname".IN","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i < n ; ++i){
        int u , v , c;cin >> u >> v >> c;
        adj[u].pb(mp(v,c));adj[v].pb(mp(u,c));
    }
    for(int i = 2 ; i <= n ; ++i)cin >> a[i].first >> a[i].second;
    dfs1(1,0);
    dfs(1,0);
    for(int i = 2 ; i <= n ; ++i)cout << f[i] << " ";
}

Compilation message (stderr)

harbingers.cpp: In member function 'll convex::query(int)':
harbingers.cpp:49:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = l + h >> 1;
                       ~~^~~
harbingers.cpp:50:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(mid + 1 < p.size() && p[mid].Val(x) >= p[mid + 1].Val(x)){
                ~~~~~~~~^~~~~~~~~~
harbingers.cpp: In function 'void update(int, int, int, int, int, point)':
harbingers.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
harbingers.cpp: In function 'll query(int, int, int, int, int)':
harbingers.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".IN","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100