제출 #1036523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036523		model_code	Petrol stations (CEOI24_stations)	C++17	38 / 100	3527 ms	2097152 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;
	vector<ll> dp_here;
	vector<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 = vector<ll>(k+1);
		dp_after_edge = vector<ll>(k+1);
		dp_here[k]+=1;
		for(auto &[nd, l] : e)
			nd->go();
		for(auto &[nd, l] : e)
			for (int i=0; i<k+1; i++)
				dp_here[i] += nd->dp_after_edge[i];
		for (int i=0; i<k+1; i++)
		{
			if(i-up.second >= 0)
				dp_after_edge[i-up.second] += dp_here[i];
			else
			{
				dp_after_edge[k-up.second] += dp_here[i];
				counts += dp_here[i]*(n-subtree_size);
			}
		}
	}
	void go2(vector<ll> dp_down)
	{
		for(auto &[nd, l] : e)
		{
			vector<ll> dp_down_nd = dp_down;
			dp_down_nd[k] += 1;
			for(auto &[nd2, l2] : e) if(nd != nd2)
				for (int i=0; i<k+1; i++)
					dp_down_nd[i] += nd2->dp_after_edge[i];
			auto dp_down_after_edge = vector<ll>(k+1);
			for (int i=0; i<k+1; i++)
			{
				if(i-l >= 0)
					dp_down_after_edge[i-l] += dp_down_nd[i];
				else
				{
					dp_down_after_edge[k-l] += dp_down_nd[i];
					counts += dp_down_nd[i]*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(vector<ll>(k+1));
	for (int i=0; i<n; i++) printf("%lld\n", nds[i].counts);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'int Node::make_rooted(Node*)':
Main.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Node*, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0; i<e.size(); i++)
      |                ~^~~~~~~~~
Main.cpp: In function 'int main(int, char**)':
Main.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   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: 12 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35