Submission #1289665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289665		loom	Petrol stations (CEOI24_stations)	C++20	26 / 100	2770 ms	2162688 KiB

Main

// Author: Jiří Kalvoda
#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int n;
ll k;

struct Node{
	vector<pair<Node*, ll>> e;
	pair<Node*, ll> up;
	ll counts=0;
	int id;
	int subtree_size;
	map<int, ll> dp_here;
	map<int, ll> dp_after_edge;
	int make_rooted(Node * _up)
	{
		subtree_size=1;
		for(int i=0; i<e.size(); i++)
		{
			if(e[i].first == _up)
			{
				up = e[i];
				e[i] = e[e.size()-1];
				e.pop_back();
			}
		}
		for(auto &[nd, l] : e)
			subtree_size += nd->make_rooted(this);
		return subtree_size;
	}
	void go()
	{
		dp_here = map<int, ll>();
		dp_after_edge = map<int, ll>();
		dp_here[k]+=1;
		for(auto &[nd, l] : e)
			nd->go();
		for(auto &[nd, l] : e)
			for(auto &[i, v] : nd->dp_after_edge)
				dp_here[i] += v;
		for(auto &[i, v] : dp_here)
		{
			if(i-up.second >= 0)
				dp_after_edge[i-up.second] += v;
			else
			{
				dp_after_edge[k-up.second] += v;
				counts += v*(n-subtree_size);
			}
		}
	}
	void go2(map<int, ll> dp_down)
	{
		for(auto &[nd, l] : e)
		{
			map<int, ll> dp_down_nd = dp_down;
			for(auto &[i, v] : dp_here)
				dp_down_nd[i] += v;
			for(auto &[i, v] : nd->dp_after_edge)
				dp_down_nd[i] -= v;
			auto dp_down_after_edge = map<int, ll>();
			for(auto &[i, v] : dp_down_nd)
			{
				if(i-l >= 0)
					dp_down_after_edge[i-l] += v;
				else
				{
					dp_down_after_edge[k-l] += v;
					counts += v*nd->subtree_size;
				}
			}
			nd->go2(dp_down_after_edge);
		}
	}
} *nds;

int main(int argc, char ** argv)
{
	scanf("%d%lld", &n, &k);
	nds = new Node[n];
	for (int i=0; i<n; i++) nds[i].id = i;
	for (int i=0; i<n-1; i++)
	{
		int a,b;
		ll l;
		scanf("%d%d%lld", &a, &b, &l);
		nds[a].e.push_back({nds+b, l});
		nds[b].e.push_back({nds+a, l});
	}
	nds[0].make_rooted(NULL);
	nds[0].go();
	nds[0].go2(map<int,ll>());
	for(int i=0; i<n; i++) printf("%lld\n", nds[i].counts);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main(int, char**)':
Main.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         scanf("%d%lld", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:89:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                 scanf("%d%d%lld", &a, &b, &l);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 18 / 18
• Subtask 2: 8 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35