Submission #1127907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127907		lamlamjjdo	Harbingers (CEOI09_harbingers)	C++20	0 / 100	139 ms	26364 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
int n;
int p[20][100010];
vector<pair<int,long long>>a[100010];
long long dp[100010];
long long s[100010],v[100010];
long long h[100010];
void pre(int i,int c){
    p[0][i]=c;
    for(int o=1;o<17;o++){
        p[o][i]=p[o-1][p[o-1][i]];
    }
    if(i!=1){
        int y=c;
        for(int o=16;o>=0;o--){
            if(p[o][y]){
                int g=p[o][y];
                if((h[i]-h[y])*v[i]+dp[y]>(h[i]-h[g])*v[i]+dp[g])y=g;
            }
        }
        int g=p[0][y];
        dp[i]=min((h[i]-h[y])*v[i]+dp[y],(h[i]-h[g])*v[i]+dp[g])+s[i];
    }
    for(auto o:a[i]){
        if(o.first==c)continue;
        h[o.first]=h[i]+o.second;
        pre(o.first,i);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen("c.INP","r")){
        freopen("c.INP","r",stdin);
        freopen("c.OUT","w",stdout);
    }
    cin >>n;
    for(int i=1;i<n;i++){
        int x,y,z;
        cin >>x>>y>>z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    for(int i=2;i<=n;i++){
        cin >>s[i]>>v[i];
    }
    dp[0]=2e18;
    pre(1,0);
    for(int i=2;i<=n;i++){
        cout <<dp[i]<<' ';
    }
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("c.INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen("c.OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100