oj.uz

Submission #1036523

# Submission time Handle Problem Language Result Execution time Memory
1036523 2024-07-27T13:31:11 Z model_code Petrol stations (CEOI24_stations) C++17
38 / 100
 3500 ms 2097152 KB 
// 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;
}

Compilation message

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 11776 KB Output is correct
4 Correct 7 ms 5992 KB Output is correct
5 Correct 55 ms 16996 KB Output is correct
6 Correct 13 ms 13016 KB Output is correct
7 Correct 11 ms 12892 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 10 ms 14212 KB Output is correct
10 Correct 9 ms 12956 KB Output is correct
11 Correct 12 ms 16604 KB Output is correct
12 Correct 12 ms 16664 KB Output is correct
13 Correct 17 ms 16740 KB Output is correct
14 Correct 279 ms 9052 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 53 ms 28720 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 53 ms 28720 KB Output is correct
5 Runtime error 1040 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 43 ms 18008 KB Output is correct
4 Correct 58 ms 37572 KB Output is correct
5 Correct 118 ms 52220 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 113 ms 24960 KB Output is correct
8 Correct 46 ms 25172 KB Output is correct
9 Correct 46 ms 25132 KB Output is correct

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 43 ms 18008 KB Output is correct
4 Correct 58 ms 37572 KB Output is correct
5 Correct 118 ms 52220 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 113 ms 24960 KB Output is correct
8 Correct 46 ms 25172 KB Output is correct
9 Correct 46 ms 25132 KB Output is correct
10 Execution timed out 3527 ms 23376 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 10 ms 11776 KB Output is correct
4 Correct 7 ms 5992 KB Output is correct
5 Correct 55 ms 16996 KB Output is correct
6 Correct 13 ms 13016 KB Output is correct
7 Correct 11 ms 12892 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 10 ms 14212 KB Output is correct
10 Correct 9 ms 12956 KB Output is correct
11 Correct 12 ms 16604 KB Output is correct
12 Correct 12 ms 16664 KB Output is correct
13 Correct 17 ms 16740 KB Output is correct
14 Correct 279 ms 9052 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 53 ms 28720 KB Output is correct
17 Runtime error 1040 ms 2097152 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -