Submission #1361432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361432		po_rag526	Harbingers (CEOI09_harbingers)	C++20	20 / 100	1096 ms	12612 KiB

harbingers

#include <bits/stdc++.h>

#define INF 3e18

using namespace std;

/* TLE naive implementation

Capital 1 (and graph is a tree)
There was ONE harbinger in each town. It has a speed of minutes per km, and also a time to start the journey.
Every time a harbinger arrives to a town, it can go to the next or give the letter to another harbinger from that town

Then, I can start saying to arrive from town 1 to town 1 is 0

From a town i at level x in the tree, where 0 is the level of capital, I have x-1 towns between i and the capital

I may need to stop on another city, not the one immediately before i

I can also simplify it, trying to choose whatever town on the path from i to capital as a stop... it could also stop in the capital, where v and s is 0 and the distance to capital is also 0
This way I have:
dp[1] = 0 (capital)
dp[i] = min(s[i] + v[i] * dist(i,j) + dp[j])

The j I can get by means of the parent of i, then parent of parent of i and so on, until reach the capital
These are all the possibilities

Use DFS and keep parents to know all the ancestors of a vertex v, and also the distance from capital 1 until current town in the DFS

I can use a Li Chao Tree to better speed.
Add a new line to a Li Chao Tree when reaching a new vertex, in the beginning of the recursion and remove at the end of the recursion
Need implementation of rollback...
Easy to make it using a stack on each node of the Li Chao Tree... keep a stack on each node, every time a better line is added, keep on top of the stack
Remove when it makes sense to remove
*/

int n; //towns
vector<pair<int,long long int>> adj[100001];
long long int s[100001]; //start time
long long int v[100001]; //minutes to travel 1km

int pi[100001];
long long int prefSumDist[100001]; /*Distance from root 1 until vertex v*/

bool visited[100001];

long long int dp[100001];


void dfs(int u) {
	/*
	Trying to compute dp[u]
	dp[u] = min(s[u] + v[u] * dist(a,u) + dp[a])
	for all ancestors 'a' from u
	dist(a,u) = prefSumDist[u] - prefSumDist[a]
	*/
	if (u != 1) {
		dp[u] = INF;

		int a = pi[u];
		while (a != -1) { //Check all the ancestors of u

			dp[u] = min(dp[u], s[u] + v[u] * (prefSumDist[u] - prefSumDist[a]) + dp[a]);

			a = pi[a];
		}

	}

	//Add u to stack
	for (int k = 0; k < adj[u].size(); k++) {
		pair<int,long long int> pairV = adj[u][k];
		if (!visited[pairV.first]) {
			visited[pairV.first] = true;
			pi[pairV.first] = u;
			prefSumDist[pairV.first] = prefSumDist[u] + pairV.second; /*The total distance from root 1 until town v is the distance until u + distance from u to v*/
			dfs(pairV.first);
		}
	}

}

int main() {
	scanf("%d ", &n);

	for (int i = 1; i < n; i++) {
		int a, b;
		long long int d;
		scanf("%d %d %lld ", &a, &b, &d);
		adj[a].push_back(make_pair(b,d));
		adj[b].push_back(make_pair(a,d));
	}

	for (int i = 2; i <= n; i++) {
		scanf("%lld %lld ", &s[i], &v[i]);
	}

	pi[1] = -1;
	dp[1] = 0;
	prefSumDist[1] = 0;
	visited[1] = true;
	dfs(1);

	printf("%lld", dp[2]);
	for (int i = 3; i <= n; i++) {
		printf(" %lld", dp[i]);
	}
	printf("\n");

	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d ", &n);
      |         ~~~~~^~~~~~~~~~~
harbingers.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 scanf("%d %d %lld ", &a, &b, &d);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:94:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                 scanf("%lld %lld ", &s[i], &v[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100