Submission #401023

#	Time	Username	Problem	Language	Result	Execution time	Memory
401023		AriaH	Magic Tree (CEOI19_magictree)	C++11	100 / 100	205 ms	100676 KiB

magictree

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, m, k, P[N], f[N], w[N], d[N];

vector < int > G[N];

map < int, ll > dp[N];

void Merge(int v, int u)
{
	if(SZ(dp[v]) < SZ(dp[u]))
	{
		dp[v].swap(dp[u]);
	}
	for(auto cu : dp[u])
	{
		if(cu.S == 0) continue;
		dp[v][cu.F] += cu.S;
	}
}

void dfs(int v)
{
	for(auto u : G[v])
	{
		dfs(u);
		Merge(v, u);
	}
	if(d[v])
	{
		dp[v][d[v]] += w[v];
		int last = d[v], x = w[v];
		while(1)
		{
			auto it = dp[v].upper_bound(last);
			if(it == dp[v].end()) break;
			last = it->F;
			int now = min(1ll * x, it->S);
			x -= now;
			it->S -= now;
			if(it->S == 0)
			{
				dp[v].erase(it);
			}
			if(x == 0) break;
		}
	}
	/*printf("v = %d\n", v);
	for(auto now : dp[v])
	{
		printf("now = %d %d\n", now.F, now.S);
	}
	*/
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 2; i <= n ;i ++)
	{
		scanf("%d", &P[i]);
		G[P[i]].push_back(i);
	}
	for(int i = 1; i <= m; i ++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		w[a] = c;
		d[a] = b;
	}
	dfs(1);
	ll tot = 0;
	for(auto x : dp[1]) tot += x.S;
	printf("%lld", tot);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   scanf("%d", &P[i]);
      |   ~~~~~^~~~~~~~~~~~~
magictree.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17