oj.uz

Submission #969177

# Submission time Handle Problem Language Result Execution time Memory
969177 2024-04-24T16:03:03 Z pan Pastiri (COI20_pastiri) C++17
100 / 100
 542 ms 98072 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define endl '\n'
#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 input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#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 all(x) x.begin(), x.end()
#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 __int128  sll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
ll const INF = 1e13;
ll n, k, a, b;
vector<ll> sheep;
vector<ll> adj[500005];
vector<ll> ans;
ll depth[500005], dist[500005], visited[500005], dp[500005], save[500005], done[500005];
 
bool compare(ll x, ll y)
{
	return depth[x] > depth[y];
}
void dfs(ll from, ll to)
{
	if (dist[to] + depth[to] > dp[to]) dp[to] = dist[to] + depth[to], save[to] = to;
	for (ll u: adj[to])
	{
		if (u==from) continue;
		depth[u] = depth[to] + 1;
		dp[u] = dp[to];
		save[u] = save[to];
		dfs(to, u);
	}
}
 
 
void mark( ll to)
{
	done[to] = true;
	for (ll u: adj[to])
	{
		if (done[u] || dist[u]!=dist[to]-1) continue;
		mark(u);
	}
}
int main()
{
	input2(n, k);
	for (ll i=0; i<n-1; ++i) 
	{
		input2(a, b);
		adj[a].pb(b);
		adj[b].pb(a);
	}
	sheep.resize(k);
	fill(dist+1, dist+n+1, INF);
	fill(visited+1, visited+n+1, 0);
	queue<ll> q;
	for (ll i=0; i<k; ++i) {input(sheep[i]); q.push(sheep[i]); dist[sheep[i]] = 0;}
	while (q.size())
	{
		ll u = q.front();
		q.pop();
		if (visited[u]) continue;
		visited[u] = true;
		for (ll x: adj[u]) if (dist[x] > dist[u] + 1) {dist[x] = dist[u] + 1; q.push(x);}
	}
	fill(dp+1, dp+n+1, -INF);
	depth[1] = 0;
	dfs(-1, 1);
	fill(done+1, done+n+1, 0);
	sort(sheep.begin(), sheep.end(), compare);
	for (ll u: sheep)
	{
		if (done[u]) continue;
		mark(save[u]);
		ans.pb(save[u]);
	}
	print(ll(ans.size()), '\n');
	for (ll u: ans) print(u, ' ');
	return 0;
}

Compilation message

pastiri.cpp: In function 'int main()':
pastiri.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
pastiri.cpp:70:2: note: in expansion of macro 'input2'
   70 |  input2(n, k);
      |  ^~~~~~
pastiri.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
pastiri.cpp:73:3: note: in expansion of macro 'input2'
   73 |   input2(a, b);
      |   ^~~~~~
pastiri.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
pastiri.cpp:81:26: note: in expansion of macro 'input'
   81 |  for (ll i=0; i<k; ++i) {input(sheep[i]); q.push(sheep[i]); dist[sheep[i]] = 0;}
      |                          ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 90336 KB Output is correct
2 Correct 173 ms 90304 KB Output is correct
3 Correct 182 ms 90288 KB Output is correct
4 Correct 272 ms 98072 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23388 KB Output is correct
2 Correct 6 ms 23388 KB Output is correct
3 Correct 333 ms 54704 KB Output is correct
4 Correct 324 ms 59592 KB Output is correct
5 Correct 420 ms 51284 KB Output is correct
6 Correct 533 ms 54852 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23132 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 5 ms 23252 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 5 ms 23132 KB Output is correct
6 Correct 6 ms 23384 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 5 ms 23160 KB Output is correct
9 Correct 5 ms 23132 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 5 ms 23128 KB Output is correct
12 Correct 6 ms 23132 KB Output is correct
13 Correct 5 ms 23132 KB Output is correct
14 Correct 5 ms 23132 KB Output is correct
15 Correct 5 ms 23132 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 55196 KB Output is correct
2 Correct 480 ms 54840 KB Output is correct
3 Correct 512 ms 58640 KB Output is correct
4 Correct 447 ms 51412 KB Output is correct
5 Correct 387 ms 53620 KB Output is correct
6 Correct 449 ms 63460 KB Output is correct
7 Correct 502 ms 61112 KB Output is correct
8 Correct 520 ms 60240 KB Output is correct
9 Correct 542 ms 51444 KB Output is correct
10 Correct 440 ms 51236 KB Output is correct
11 Correct 384 ms 57408 KB Output is correct
12 Correct 314 ms 59824 KB Output is correct
13 Correct 322 ms 62376 KB Output is correct
14 Correct 278 ms 58020 KB Output is correct
15 Correct 39 ms 32656 KB Output is correct
16 Correct 464 ms 50468 KB Output is correct
17 Correct 310 ms 54368 KB Output is correct
18 Correct 421 ms 48524 KB Output is correct
19 Correct 471 ms 60892 KB Output is correct
20 Correct 463 ms 65576 KB Output is correct
21 Correct 390 ms 53868 KB Output is correct
22 Correct 422 ms 54496 KB Output is correct