oj.uz

답안 #925211

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925211 2024-02-11T03:25:27 Z pan Firefighting (NOI20_firefighting) C++17
36 / 100
 237 ms 36084 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 = 1e13;
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, ' ');
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 27928 KB Output is correct
2 Correct 207 ms 27844 KB Output is correct
3 Correct 56 ms 15048 KB Output is correct
4 Correct 237 ms 28336 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7272 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7256 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 7272 KB Output is correct
12 Correct 2 ms 7256 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 7512 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 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 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7516 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 7256 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 3 ms 7260 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 7480 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7260 KB Output is correct
21 Correct 2 ms 7260 KB Output is correct
22 Correct 2 ms 7256 KB Output is correct
23 Correct 2 ms 7260 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

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 28728 KB Output is correct
2 Correct 81 ms 17608 KB Output is correct
3 Correct 110 ms 20680 KB Output is correct
4 Correct 71 ms 18892 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 173 ms 31156 KB Output is correct
8 Correct 159 ms 31940 KB Output is correct
9 Correct 156 ms 31980 KB Output is correct
10 Correct 158 ms 31588 KB Output is correct
11 Correct 228 ms 36084 KB Output is correct
12 Correct 130 ms 23768 KB Output is correct
13 Correct 61 ms 17492 KB Output is correct
14 Correct 112 ms 22476 KB Output is correct
15 Correct 135 ms 25576 KB Output is correct
16 Correct 159 ms 26828 KB Output is correct
17 Correct 131 ms 24156 KB Output is correct
18 Correct 112 ms 23376 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Incorrect 2 ms 7516 KB Integer parameter [name=F] equals to 0, violates the range [1, 1199]
4 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 22864 KB Output is correct
2 Correct 163 ms 22096 KB Output is correct
3 Incorrect 166 ms 23324 KB Integer parameter [name=F] equals to 0, violates the range [1, 298259]
4 Halted 0 ms 0 KB -