Submission #937118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
937118	2024-03-03T13:49:46 Z	amirhoseinfar1385	Harbingers (CEOI09_harbingers)	C++17	20 / 100	1000 ms	22352 KB

harbingers

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long inf=1e18;
struct func{
	long long fas,shib;
	long long inersect(func f){
		long long sor=fas-f.fas,makh=f.shib-shib;
		if(makh==0){
			if(sor>0){
				return -inf;
			}
			return inf;
		}
		if(makh<0){
			makh*=-1;
			sor*=-1;
		}
		if(sor<0){
			return sor/makh;
		}
		return (sor+makh-1)/makh;
	}
};
struct yal{
	long long u,v,w;
	long long getad(long long fu){
		return (u^v^fu);
	}
}alle[maxn];
long long n,timea=0,high[maxn],para[maxn],dp[maxn];
pair<long long,long long>stf[maxn],all[maxn];
vector<long long>adj[maxn];

void dfs(long long u,long long par=0,long long len=0){
	timea++;
	para[u]=par;
	high[u]=len;
	stf[u].first=timea;
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v!=par){
			dfs(v,u,len+alle[x].w);
		}
	}
	stf[u].second=timea;
}

void vorod(){
	cin>>n;
	for(long long i=0;i<n-1;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].w;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
	}
	for(long long i=2;i<=n;i++){
		cin>>all[i].first>>all[i].second;
	}
}

void pre(){
	dfs(1);
}

void upd(long long u){
	dp[u]=high[u]*all[u].second;
	long long fu=para[u];
	while(fu!=0){
		dp[u]=min(dp[u],dp[fu]+all[u].second*high[u]-all[u].second*high[fu]);
		fu=para[fu];
	}
	dp[u]+=all[u].first;
}

void solve(long long u=1){
	upd(u);
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v!=para[u]){
			solve(v);
		}
	}
}

void khor(){
	for(long long i=2;i<=n;i++){
		cout<<dp[i]<<" ";
	}
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

Subtask #1

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8796 KB	Output is correct
2	Correct	13 ms	9136 KB	Output is correct
3	Execution timed out	1002 ms	14160 KB	Time limit exceeded
4	Execution timed out	1046 ms	16724 KB	Time limit exceeded
5	Execution timed out	1079 ms	19812 KB	Time limit exceeded
6	Execution timed out	1053 ms	22352 KB	Time limit exceeded
7	Execution timed out	1054 ms	15500 KB	Time limit exceeded
8	Execution timed out	1103 ms	18636 KB	Time limit exceeded
9	Execution timed out	1061 ms	20136 KB	Time limit exceeded
10	Execution timed out	1060 ms	19344 KB	Time limit exceeded