oj.uz

Submission #925212

# Submission time Handle Problem Language Result Execution time Memory
925212 2024-02-11T03:28:41 Z pan Firefighting (NOI20_firefighting) C++17
100 / 100
 275 ms 44884 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll const INF = ll(1e16);
ll n, k, x, y, z;
vector<pi> adj[300005];
vector<ll> ans;
pi dfs(ll p, ll from, ll dist)
{
	ll overflow = -INF, underflow = 0;
	for (pi u: adj[from])
	{
		if (u.f==p) continue;
		pi ret = dfs(from, u.f, u.s);
		if (ret.f==0) underflow = max(underflow, ret.s);
		if (ret.f==1) overflow = max(overflow, ret.s);
	}
	pi ret;
	if (overflow>=underflow) {ret = mp(1, overflow - dist);}
	else
	{
		if (underflow+dist>k)
		{
			ans.pb(from);
			ret = mp(1, k-dist);
		}
		else
		{
			ret = mp(0, underflow + dist);
		}
	}
	if (ret.f && ret.s<0) ret= mp(0, 0); // reset from overflow to underflow
	//show2(ret.f, ret.s);
	return ret;
	
}
int main()
{
	input(n); input(k);
	for (ll i=0; i<n-1; ++i)
	{
		input(x); input(y); input(z);
		adj[x].pb(mp(y,z));
		adj[y].pb(mp(x,z));
	}
	dfs(-1, 1, INF);
	print((ll) ans.size(), '\n');
	for (ll u: ans) print(u, ' ');
	printf("%c", '\n');
	return 0;
}

Compilation message

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Firefighting.cpp:65:2: note: in expansion of macro 'input'
   65 |  input(n); input(k);
      |  ^~~~~
Firefighting.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Firefighting.cpp:65:12: note: in expansion of macro 'input'
   65 |  input(n); input(k);
      |            ^~~~~
Firefighting.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Firefighting.cpp:68:3: note: in expansion of macro 'input'
   68 |   input(x); input(y); input(z);
      |   ^~~~~
Firefighting.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Firefighting.cpp:68:13: note: in expansion of macro 'input'
   68 |   input(x); input(y); input(z);
      |             ^~~~~
Firefighting.cpp:14:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
Firefighting.cpp:68:23: note: in expansion of macro 'input'
   68 |   input(x); input(y); input(z);
      |                       ^~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 28000 KB Output is correct
2 Correct 203 ms 28976 KB Output is correct
3 Correct 56 ms 15048 KB Output is correct
4 Correct 266 ms 27796 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7472 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7460 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7256 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 2 ms 7260 KB Output is correct
19 Correct 2 ms 7468 KB Output is correct
20 Correct 2 ms 7256 KB Output is correct
21 Correct 2 ms 7260 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7264 KB Output is correct
24 Correct 2 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 27852 KB Output is correct
2 Correct 101 ms 17872 KB Output is correct
3 Correct 103 ms 17860 KB Output is correct
4 Correct 76 ms 16592 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 203 ms 26272 KB Output is correct
8 Correct 169 ms 26548 KB Output is correct
9 Correct 160 ms 26292 KB Output is correct
10 Correct 160 ms 27696 KB Output is correct
11 Correct 207 ms 28096 KB Output is correct
12 Correct 117 ms 20524 KB Output is correct
13 Correct 64 ms 15424 KB Output is correct
14 Correct 103 ms 19400 KB Output is correct
15 Correct 139 ms 21960 KB Output is correct
16 Correct 160 ms 23140 KB Output is correct
17 Correct 120 ms 20424 KB Output is correct
18 Correct 137 ms 20228 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 4 ms 7784 KB Output is correct
6 Correct 3 ms 7768 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 3 ms 7772 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7772 KB Output is correct
11 Correct 3 ms 7772 KB Output is correct
12 Correct 3 ms 7512 KB Output is correct
13 Correct 4 ms 7772 KB Output is correct
14 Correct 3 ms 7768 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Correct 3 ms 7488 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 4 ms 7516 KB Output is correct
19 Correct 4 ms 7848 KB Output is correct
20 Correct 3 ms 7516 KB Output is correct
21 Correct 3 ms 7516 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 23016 KB Output is correct
2 Correct 202 ms 22112 KB Output is correct
3 Correct 180 ms 23160 KB Output is correct
4 Correct 70 ms 17688 KB Output is correct
5 Correct 203 ms 40480 KB Output is correct
6 Correct 240 ms 39008 KB Output is correct
7 Correct 243 ms 42696 KB Output is correct
8 Correct 197 ms 41732 KB Output is correct
9 Correct 211 ms 36788 KB Output is correct
10 Correct 207 ms 36080 KB Output is correct
11 Correct 233 ms 44884 KB Output is correct
12 Correct 113 ms 22612 KB Output is correct
13 Correct 217 ms 38600 KB Output is correct
14 Correct 226 ms 35512 KB Output is correct
15 Correct 223 ms 30836 KB Output is correct
16 Correct 234 ms 28752 KB Output is correct
17 Correct 165 ms 28500 KB Output is correct
18 Correct 183 ms 30036 KB Output is correct
19 Correct 117 ms 23304 KB Output is correct
20 Correct 60 ms 16304 KB Output is correct
21 Correct 199 ms 30292 KB Output is correct