답안 #955383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955383	2024-03-30T10:12:41 Z	Unforgettablepl	Harbingers (CEOI09_harbingers)	C++17	60 / 100	210 ms	45908 KB

harbingers

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

struct line{
    int32_t m;int n;
    line(int m,int n):m(m),n(n){}
    line(){}
    int operator()(int x) const{
        return m*x+n;
    }
};

struct node{
    node *left,*right;
    int32_t L,R;
    int32_t lin;
    node(int L,int R): L(L), R(R), left(nullptr), right(nullptr), lin(0){}
};

line lines[100001];

int query(node* curr,int x){
    if(curr==nullptr)return INF;
    int mid = (curr->L+curr->R)/2;
    if(mid==x)return lines[curr->lin](x);
    if(mid<x)return min(lines[curr->lin](x), query(curr->right, x));
    return min(lines[curr->lin](x), query(curr->left, x));
}

void update(node* curr,int32_t x, vector<pair<node*,int32_t>> &updates){
    int mid = (curr->L+curr->R)/2;
    bool betterleft = lines[curr->lin](curr->L) > lines[x](curr->L);
    bool betterright = lines[curr->lin](curr->R) > lines[x](curr->R);
    bool bettermid = lines[curr->lin](mid) > lines[x](mid);
    if(!(betterleft or bettermid or betterright))return;
    if(bettermid and betterright and betterleft) {
        updates.emplace_back(curr,curr->lin);
        swap(x, curr->lin);
    }
    else if(betterleft and !bettermid){
        if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
        update(curr->left,x,updates);
    } else if(!bettermid){
        if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
        update(curr->right,x,updates);
    } else if(betterleft){
        updates.emplace_back(curr,curr->lin);
        swap(curr->lin,x);
        if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
        update(curr->right,x,updates);
    } else {
        updates.emplace_back(curr,curr->lin);
        swap(curr->lin, x);
        if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
        update(curr->left,x,updates);
    }
}



int DP[100001];
int32_t S[100001];
int32_t V[100001];
vector<pair<int32_t,int32_t>> adj[100001];
node* head = new node(1,1e9);

void dfs(int x,int p,int depth){
    DP[x] = S[x]+V[x]*depth+ query(head,V[x]);
    vector<pair<node*,int32_t>> updates;
    lines[x] = line(-depth,DP[x]);
    update(head,x,updates);
    for(auto&i:adj[x])if(i.first!=p){
        dfs(i.first,x,depth+i.second);
    }
    for(auto&i:updates)i.first->lin=i.second;
}

int32_t main(){
//    freopen("harbingers.in","r",stdin);
//    freopen("harbingers.out","w",stdout);
    int n;
    cin >> n;
    for(int i=1;i<n;i++){
        int u,v,d;cin>>u>>v>>d;
        adj[u].emplace_back(v,d);
        adj[v].emplace_back(u,d);
    }
    for(int i=2;i<=n;i++)cin>>S[i]>>V[i];
    vector<pair<node*,int32_t>> h;
    lines[0] = line(0,0);
    update(head,0,h);
    dfs(1,0,0);
    for(int i=2;i<n;i++)cout<<DP[i]<<' ';
    cout << DP[n] << '\n';
}

Compilation message

harbingers.cpp: In constructor 'node::node(long long int, long long int)':
harbingers.cpp:19:15: warning: 'node::R' will be initialized after [-Wreorder]
   19 |     int32_t L,R;
      |               ^
harbingers.cpp:18:11: warning:   'node* node::left' [-Wreorder]
   18 |     node *left,*right;
      |           ^~~~
harbingers.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     node(int L,int R): L(L), R(R), left(nullptr), right(nullptr), lin(0){}
      |     ^~~~

Subtask #1

60.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4700 KB	Output is correct
2	Correct	4 ms	5212 KB	Output is correct
3	Correct	74 ms	20584 KB	Output is correct
4	Runtime error	133 ms	45392 KB	Memory limit exceeded
5	Correct	130 ms	24608 KB	Output is correct
6	Correct	144 ms	25168 KB	Output is correct
7	Correct	102 ms	13804 KB	Output is correct
8	Runtime error	173 ms	36456 KB	Memory limit exceeded
9	Runtime error	210 ms	45908 KB	Memory limit exceeded
10	Runtime error	167 ms	42700 KB	Memory limit exceeded