oj.uz

Submission #540129

# Submission time Handle Problem Language Result Execution time Memory
540129 2022-03-19T10:08:42 Z hhhhaura Pastiri (COI20_pastiri) C++14
100 / 100
 974 ms 108628 KB 
#define wiwihorz
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define int long long int 
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L)==R], ++L;}
void kout(){cerr<< endl;}
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	int n;
	vector<vector<int>> mp, mp1;
	vector<int> dep, dis, a, v, vis, par;
	void init_(int _n) {
		n = _n;
		mp.assign(n + 1, vector<int>());
		mp1.assign(n + 1, vector<int>());
		dep.assign(n + 1, 0);
		dis.assign(n + 1, INF);
		vis.assign(n + 1, 0);
		par.assign(n + 1, 0);
		a.assign(n + 1, 0);
		v.assign(n, 0);
		iota(all(v), 1);
	}
	void dfs(int x, int p, int d) {
		par[x] = p, dep[x] = d;
		for(auto i : mp[x]) if(i != p) dfs(i, x, d + 1);
	}
	void dfs1(int x) {
		vis[x] = 1;
		for(auto i : mp1[x]) 
			if(!vis[i]) dfs1(i);
	}
	void solve() {
		queue<int> q;
		rep(i, 1, n) if(a[i]) {
			q.push(i);
			dis[i] = 0;
		}
		while(q.size()) {
			int cur = q.front();
			q.pop();
			for(auto i : mp[cur]) {
				if(dis[i] == INF) {
					dis[i] = dis[cur] + 1;
					q.push(i);
				}
			}
		}
		rep(i, 1, n) for(auto j : mp[i]) 
			if(dis[j] + 1 == dis[i]) mp1[i].push_back(j);
		vector<int> ans;
		dfs(1, 1, 0);
		sort(all(v), [&](int a, int b) {
			return dep[a] > dep[b];
		});
		for(auto i : v) if(!vis[i] && a[i]) {
			int cur = i;
			while(cur != 1 && dis[par[cur]] 
				>= dep[i] - dep[par[cur]]) cur = par[cur];
			assert(!vis[cur]);
			dfs1(cur);
			ans.push_back(cur);
		}
		cout << ans.size() << "\n";
		rep(i, 0, signed(ans.size()) - 1)
			cout << ans[i] << " \n"[i + 1 == ans.size()];
	}
	
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k;
	cin >> n >> k;
	init_(n);
	rep(i, 1, n - 1) {
		int a, b;
		cin >> a >> b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	rep(i, 1, k) {
		int x; cin >> x;
		a[x] = 1;
	}
	solve();
	return 0;
}

Compilation message

pastiri.cpp:17:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L)==R], ++L;}
      |             ^~~~
pastiri.cpp:17:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L)==R], ++L;}
      |                    ^~~~
pastiri.cpp: In function 'void solver::solve()':
pastiri.cpp:82:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    cout << ans[i] << " \n"[i + 1 == ans.size()];
      |                            ~~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 102000 KB Output is correct
2 Correct 267 ms 108628 KB Output is correct
3 Correct 257 ms 108620 KB Output is correct
4 Correct 267 ms 104840 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 590 ms 87876 KB Output is correct
4 Correct 598 ms 92508 KB Output is correct
5 Correct 738 ms 85256 KB Output is correct
6 Correct 904 ms 87308 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 572 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 81268 KB Output is correct
2 Correct 749 ms 87808 KB Output is correct
3 Correct 702 ms 85152 KB Output is correct
4 Correct 760 ms 84972 KB Output is correct
5 Correct 481 ms 66428 KB Output is correct
6 Correct 669 ms 87464 KB Output is correct
7 Correct 763 ms 86516 KB Output is correct
8 Correct 776 ms 86632 KB Output is correct
9 Correct 974 ms 85228 KB Output is correct
10 Correct 771 ms 85240 KB Output is correct
11 Correct 586 ms 89772 KB Output is correct
12 Correct 500 ms 88052 KB Output is correct
13 Correct 496 ms 87444 KB Output is correct
14 Correct 590 ms 90612 KB Output is correct
15 Correct 60 ms 14120 KB Output is correct
16 Correct 782 ms 78236 KB Output is correct
17 Correct 490 ms 68220 KB Output is correct
18 Correct 678 ms 69912 KB Output is correct
19 Correct 756 ms 89644 KB Output is correct
20 Correct 806 ms 93152 KB Output is correct
21 Correct 696 ms 87716 KB Output is correct
22 Correct 756 ms 88008 KB Output is correct