Submission #1323602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323602		iamsazidh	Tree (IOI24_tree)	C++20	7 / 100	53 ms	21272 KiB

tree

#include "tree.h"
// ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
// Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
#define spc " "

#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array)                      \
	for (int w = 0; w < array.size(); w++) \
		cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif

const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);

int n;
std::vector<int> p, w;

vi cnt;

ll leaf = 0;

int dfs(vii &adj, int i, vi &W)
{
	if (adj[i].size() == 0)
	{
		leaf++;
		return 1;
	}
	int c = 0;
	for (auto x : adj[i])
	{
		c += dfs(adj, x, W);
	}
	if (W[i] == 0)
	{
		cnt[c]++;
		return 1;
	}
	else
	{
		return c;
	}
}

void init(std::vector<int> P, std::vector<int> W)
{
	n = P.size();
	cnt.resize(n + 5);
	vii adj(n + 1);
	for (int i = 1; i < n; i++)
		adj[P[i]].push_back(i);
	cnt[dfs(adj, 0, W)];
	for (int i = 1; i <= n; i++)
		cnt[i] += cnt[i - 1];
}

long long query(int L, int R)
{
	ll l = L, r = R;
	ll cost = (leaf * l) + (max(0LL, (leaf * l)-r));
	// int k = R/L;
	// k = min(k, n);
	// cost -= cnt[n]*(l);
	// cost += cnt[k]*l + (r*(cnt[n]- (k<1 ? 0 : cnt[k-1]) ));
	return cost;

}

Compilation message (stderr)

tree.cpp: In function 'void init(std::vector<int>, std::vector<int>)':
tree.cpp:76:27: warning: ignoring return value of 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]', declared with attribute 'nodiscard' [-Wunused-result]
   76 |         cnt[dfs(adj, 0, W)];
      |                           ^
In file included from /usr/include/c++/13/vector:66,
                 from tree.h:1,
                 from tree.cpp:1:
/usr/include/c++/13/bits/stl_vector.h:1126:7: note: declared here
 1126 |       operator[](size_type __n) _GLIBCXX_NOEXCEPT
      |       ^~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19