제출 #1283129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283129		herominhsteve	Harbingers (CEOI09_harbingers)	C++20	20 / 100	103 ms	131072 KiB

harbingers

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "harbingers"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 1e5 + 5;

struct MinHull{
	struct Line{
		long long a,b;
		Line():a(0),b(0) {}
		Line(long long A,long long B):a(A),b(B) {}
		friend double getIntersection(const Line &x, const Line &y){
			return 1.0 * (y.b - x.b) / (x.a - y.a);
		}
		friend bool overlap(Line A,Line B,Line C){
			return getIntersection(B,C) < getIntersection(A,C);
		}
		long long evaluate(long long x){
			return a * x + b;
		}
	};

	vector<Line> lines;
	vector<double> bubble;

	void addLine(long long a, long long b){
		Line newLine = Line(a,b);
		while (lines.size() >= 2 and overlap(lines[lines.size()-2], lines.back(), newLine)){
			lines.pop_back();
			bubble.pop_back();
		}
		if (!lines.empty()){
			bubble.emplace_back(getIntersection(lines.back() , newLine));
		}
		lines.emplace_back(newLine);
	}

	long long getVal(long long x){
        if (lines.empty()) return 0;
		int pos = lower_bound(allof(bubble),x) - bubble.begin();
		return lines[pos].evaluate(x);
	}

};

struct Edges{
    int v;
    long long w;
    Edges(int V,long long W):v(V),w(W){}
};

int n;
vector<Edges> graph[MAXN];
vector<long long> S,V;

void init(){
    cin>>n;
    for (int i=1;i<n;i++){
        int u,v;
        long long w;
        cin>>u>>v>>w;
        graph[u].emplace_back(v,w);
        graph[v].emplace_back(u,w);
    }
    S.assign(n+1,0);
    V.assign(n+1,0);
    for (int i=2;i<=n;i++) cin>>S[i]>>V[i];
}

vector<long long> distancia;

void dfsCalDis(int u=1,int pre=-1){
    for (Edges x : graph[u]){
        if (x.v == pre) continue;
        distancia[x.v] = distancia[u] + x.w;
        dfsCalDis(x.v,u);
    }
}

vector<long long> dp;

/*
 * dp[v] = min_j (dp[u] + (dis[u][v]) * V[v] + S[v])
 * dp[v] = min_j (dp[u] + dis[u][v] * V[v]) + S[v]
 * dis[u][v] = dis[v] - dis[u]
 * dp[v] = min_j (dp[u] + dis[v] * V[v] - dis[u] * V[v]) + S[v]
 * dp[v] = min_j (dp[u] - dis[u] * V[v]) + dis[v] * V[v] + S[v]
 * dp[v] = min_j (-dis[u] * V[v] + dp[u]) + dis[v] * V[v] + S[v]
 * a = -dis[u]; b = dp[u]
*/

void dfs(int u,int pre, MinHull &cht){
    MinHull newCHT = cht;
    dp[u] = newCHT.getVal(V[u]) + distancia[u] * V[u] + S[u];
    newCHT.addLine(-distancia[u] , dp[u]);
    for (Edges x : graph[u]){
        int v = x.v;
        if (v==pre) continue;
        dfs(v,u,newCHT);
    }
}

void sol(){
    distancia.assign(n+1,0);
    dfsCalDis();
	dp.assign(n+1,0);
    MinHull cht;
    dfs(1,1,cht);
    for (int i=2;i<=n;i++) cout<<dp[i]<<" ";
}

int main(){
    setup();
    init();
    sol();
}

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp: In function 'void setup()':
harbingers.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100