Submission #954374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954374	2024-03-27T17:36:25 Z	TAhmed33	Paths (RMI21_paths)	C++	Compilation error	0 ms	0 KB

Main

#include <bits/stdc++.h>
using namespace std;
const ll inf = 1e16;
const int MAXN = 1e5 + 25;
vector <pair <int, ll>> adj[MAXN];
pair <ll, ll> dp[MAXN], dq[MAXN];
ll edge[MAXN];
int n, k;
void dfs (int pos, int par) {
	if ((int)adj[pos].size() == 1) {
		dp[pos] = {edge[pos], pos};
		return;
	}
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		edge[j.first] = j.second;
		dfs(j.first, pos);
		dp[pos] = max(dp[pos], dp[j.first]);
	}
	dp[pos].first += edge[pos];
}
void dfs2 (int pos, int par, pair <ll, ll> x = {}) {
	dq[pos] = {x.first + edge[pos], x.second};
	deque <pair <ll, ll>> u;
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		u.push_back(dp[j.first]);
	}
	for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		u.pop_front();
		auto g = x; if (!u.empty()) g = max(g, u.front());
		dfs2(j.first, pos, max(x, g));
		x = max(g, dp[j.first]);
	}
}
struct DS {
	ll val[MAXN];
	void upd (int a, ll b) {
		val[a] += b;
	}
	ll get () {
		vector <ll> d;
		for (int i = 1; i <= n; i++) d.push_back(val[i]);
		sort(d.begin(), d.end());
		reverse(d.begin(), d.end());
		ll sum = 0;
		for (int i = 0; i < k; i++) sum += d[i];
		return sum;
	}
} cur;
ll ans[MAXN];
void dfs3 (int pos, int par) {
	if (par != -1) {
		cur.upd(dp[pos].second, -edge[pos]);
		cur.upd(dq[pos].second, edge[pos]);
	}
	ans[pos] = cur.get();
	for (auto j : adj[pos]) {
		if (j.first != par) {
			dfs3(j.first, pos);
		}
	}
	if (par != -1) {
		cur.upd(dq[pos].second, -edge[pos]);
		cur.upd(dp[pos].second, edge[pos]);
	}
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	if (n == 1) {
		cout << "0\n";
		return 0;
	}
	if (n == 2) {
		int a, b, c; cin >> a >> b >> c;
		cout << c << '\n' << c << '\n';
		return 0;
	}
	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	int root = -1;
	for (int i = 1; i <= n; i++) {
		if ((int)adj[i].size() >= 2) root = i;
	}
	//cout << root << '\n';
	dfs(root, -1);
	dfs2(root, -1);
	/*for (int i = 1; i <= n; i++) {
		cout << i << " " << edge[i] << ": ";
		cout << dp[i].first << " " << dp[i].second << " || " << dq[i].first << " " << dq[i].second << '\n';
	}*/
	for (int i = 1; i <= n; i++) {
		if (i != root) {
			cur.upd(dp[i].second, edge[i]);
		}
	}
	dfs3(root, -1);
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message

Main.cpp:3:7: error: 'll' does not name a type
    3 | const ll inf = 1e16;
      |       ^~
Main.cpp:5:20: error: 'll' was not declared in this scope
    5 | vector <pair <int, ll>> adj[MAXN];
      |                    ^~
Main.cpp:5:20: error: template argument 2 is invalid
Main.cpp:5:22: error: template argument 1 is invalid
    5 | vector <pair <int, ll>> adj[MAXN];
      |                      ^~
Main.cpp:5:22: error: template argument 2 is invalid
Main.cpp:6:7: error: 'll' was not declared in this scope
    6 | pair <ll, ll> dp[MAXN], dq[MAXN];
      |       ^~
Main.cpp:6:11: error: 'll' was not declared in this scope
    6 | pair <ll, ll> dp[MAXN], dq[MAXN];
      |           ^~
Main.cpp:6:13: error: template argument 1 is invalid
    6 | pair <ll, ll> dp[MAXN], dq[MAXN];
      |             ^
Main.cpp:6:13: error: template argument 2 is invalid
Main.cpp:7:1: error: 'll' does not name a type
    7 | ll edge[MAXN];
      | ^~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:10:20: error: request for member 'size' in 'adj[pos]', which is of non-class type 'int'
   10 |  if ((int)adj[pos].size() == 1) {
      |                    ^~~~
Main.cpp:11:14: error: 'edge' was not declared in this scope
   11 |   dp[pos] = {edge[pos], pos};
      |              ^~~~
Main.cpp:11:28: error: cannot convert '<brace-enclosed initializer list>' to 'int' in assignment
   11 |   dp[pos] = {edge[pos], pos};
      |                            ^
Main.cpp:14:23: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   14 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin' declared here
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
Main.cpp:14:23: error: 'end' was not declared in this scope; did you mean 'std::end'?
   14 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::end
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end' declared here
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
Main.cpp:16:3: error: 'edge' was not declared in this scope
   16 |   edge[j.first] = j.second;
      |   ^~~~
Main.cpp:20:10: error: request for member 'first' in 'dp[pos]', which is of non-class type 'int'
   20 |  dp[pos].first += edge[pos];
      |          ^~~~~
Main.cpp:20:19: error: 'edge' was not declared in this scope
   20 |  dp[pos].first += edge[pos];
      |                   ^~~~
Main.cpp: At global scope:
Main.cpp:22:36: error: 'll' was not declared in this scope
   22 | void dfs2 (int pos, int par, pair <ll, ll> x = {}) {
      |                                    ^~
Main.cpp:22:40: error: 'll' was not declared in this scope
   22 | void dfs2 (int pos, int par, pair <ll, ll> x = {}) {
      |                                        ^~
Main.cpp:22:42: error: template argument 1 is invalid
   22 | void dfs2 (int pos, int par, pair <ll, ll> x = {}) {
      |                                          ^
Main.cpp:22:42: error: template argument 2 is invalid
Main.cpp: In function 'void dfs2(int, int, int)':
Main.cpp:23:15: error: request for member 'first' in 'x', which is of non-class type 'int'
   23 |  dq[pos] = {x.first + edge[pos], x.second};
      |               ^~~~~
Main.cpp:23:23: error: 'edge' was not declared in this scope
   23 |  dq[pos] = {x.first + edge[pos], x.second};
      |                       ^~~~
Main.cpp:23:36: error: request for member 'second' in 'x', which is of non-class type 'int'
   23 |  dq[pos] = {x.first + edge[pos], x.second};
      |                                    ^~~~~~
Main.cpp:23:42: error: cannot convert '<brace-enclosed initializer list>' to 'int' in assignment
   23 |  dq[pos] = {x.first + edge[pos], x.second};
      |                                          ^
Main.cpp:24:15: error: 'll' was not declared in this scope
   24 |  deque <pair <ll, ll>> u;
      |               ^~
Main.cpp:24:19: error: template argument 1 is invalid
   24 |  deque <pair <ll, ll>> u;
      |                   ^~
Main.cpp:24:21: error: template argument 1 is invalid
   24 |  deque <pair <ll, ll>> u;
      |                     ^~
Main.cpp:24:21: error: template argument 2 is invalid
Main.cpp:25:23: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   25 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin' declared here
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
Main.cpp:25:23: error: 'end' was not declared in this scope; did you mean 'std::end'?
   25 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::end
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end' declared here
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
Main.cpp:27:5: error: request for member 'push_back' in 'u', which is of non-class type 'int'
   27 |   u.push_back(dp[j.first]);
      |     ^~~~~~~~~
Main.cpp:29:22: error: request for member 'size' in 'u', which is of non-class type 'int'
   29 |  for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
      |                      ^~~~
Main.cpp:29:48: error: invalid types 'int[int]' for array subscript
   29 |  for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
      |                                                ^
Main.cpp:29:59: error: invalid types 'int[int]' for array subscript
   29 |  for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
      |                                                           ^
Main.cpp:29:65: error: invalid types 'int[int]' for array subscript
   29 |  for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
      |                                                                 ^
Main.cpp:30:23: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   30 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin' declared here
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
Main.cpp:30:23: error: 'end' was not declared in this scope; did you mean 'std::end'?
   30 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::end
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end' declared here
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
Main.cpp:32:5: error: request for member 'pop_front' in 'u', which is of non-class type 'int'
   32 |   u.pop_front();
      |     ^~~~~~~~~
Main.cpp:33:22: error: request for member 'empty' in 'u', which is of non-class type 'int'
   33 |   auto g = x; if (!u.empty()) g = max(g, u.front());
      |                      ^~~~~
Main.cpp:33:44: error: request for member 'front' in 'u', which is of non-class type 'int'
   33 |   auto g = x; if (!u.empty()) g = max(g, u.front());
      |                                            ^~~~~
Main.cpp: At global scope:
Main.cpp:39:2: error: 'll' does not name a type
   39 |  ll val[MAXN];
      |  ^~
Main.cpp:40:19: error: 'll' has not been declared
   40 |  void upd (int a, ll b) {
      |                   ^~
Main.cpp:43:2: error: 'll' does not name a type
   43 |  ll get () {
      |  ^~
Main.cpp: In member function 'void DS::upd(int, int)':
Main.cpp:41:3: error: 'val' was not declared in this scope
   41 |   val[a] += b;
      |   ^~~
Main.cpp: At global scope:
Main.cpp:53:1: error: 'll' does not name a type
   53 | ll ans[MAXN];
      | ^~
Main.cpp: In function 'void dfs3(int, int)':
Main.cpp:56:19: error: request for member 'second' in 'dp[pos]', which is of non-class type 'int'
   56 |   cur.upd(dp[pos].second, -edge[pos]);
      |                   ^~~~~~
Main.cpp:56:28: error: 'edge' was not declared in this scope
   56 |   cur.upd(dp[pos].second, -edge[pos]);
      |                            ^~~~
Main.cpp:57:19: error: request for member 'second' in 'dq[pos]', which is of non-class type 'int'
   57 |   cur.upd(dq[pos].second, edge[pos]);
      |                   ^~~~~~
Main.cpp:59:2: error: 'ans' was not declared in this scope; did you mean 'abs'?
   59 |  ans[pos] = cur.get();
      |  ^~~
      |  abs
Main.cpp:59:17: error: 'struct DS' has no member named 'get'
   59 |  ans[pos] = cur.get();
      |                 ^~~
Main.cpp:60:23: error: 'begin' was not declared in this scope; did you mean 'std::begin'?
   60 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin' declared here
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
Main.cpp:60:23: error: 'end' was not declared in this scope; did you mean 'std::end'?
   60 |  for (auto j : adj[pos]) {
      |                       ^
      |                       std::end
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: 'std::end' declared here
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
Main.cpp:66:19: error: request for member 'second' in 'dq[pos]', which is of non-class type 'int'
   66 |   cur.upd(dq[pos].second, -edge[pos]);
      |                   ^~~~~~
Main.cpp:66:28: error: 'edge' was not declared in this scope
   66 |   cur.upd(dq[pos].second, -edge[pos]);
      |                            ^~~~
Main.cpp:67:19: error: request for member 'second' in 'dp[pos]', which is of non-class type 'int'
   67 |   cur.upd(dp[pos].second, edge[pos]);
      |                   ^~~~~~
Main.cpp: In function 'int main()':
Main.cpp:84:10: error: request for member 'push_back' in 'adj[a]', which is of non-class type 'int'
   84 |   adj[a].push_back({b, c});
      |          ^~~~~~~~~
Main.cpp:85:10: error: request for member 'push_back' in 'adj[b]', which is of non-class type 'int'
   85 |   adj[b].push_back({a, c});
      |          ^~~~~~~~~
Main.cpp:89:19: error: request for member 'size' in 'adj[i]', which is of non-class type 'int'
   89 |   if ((int)adj[i].size() >= 2) root = i;
      |                   ^~~~
Main.cpp:100:18: error: request for member 'second' in 'dp[i]', which is of non-class type 'int'
  100 |    cur.upd(dp[i].second, edge[i]);
      |                  ^~~~~~
Main.cpp:100:26: error: 'edge' was not declared in this scope
  100 |    cur.upd(dp[i].second, edge[i]);
      |                          ^~~~
Main.cpp:105:11: error: 'ans' was not declared in this scope; did you mean 'abs'?
  105 |   cout << ans[i] << '\n';
      |           ^~~
      |           abs