| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745387 |
2023-05-19T23:51:35 Z |
nvujica |
Pastiri (COI20_pastiri) |
C++14 |
|
370 ms |
213368 KB |
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 5e5 + 10;
int n, k;
int ovca[maxn];
int d[maxn];
int u[maxn];
vector <int> v[maxn];
int dp[maxn][3];
int sta[maxn][3];
vector <int> ans;
int rek(int x, int p){
if(ovca[x]) d[x] = 0;
else d[x] = maxn;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
d[x] = min(d[x], rek(x2, x) + 1);
}
return d[x];
}
int rek2(int x, int p){
if(ovca[x]) u[x] = 0;
vector <int> t;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
t.push_back(d[x2]);
}
t.push_back(maxn);
sort(t.begin(), t.end());
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(d[x2] == t[0]) u[x2] = min(u[x] + 1, t[1] + 2);
else u[x2] = min(u[x] + 1, t[0] + 2);
rek2(x2, x);
}
}
void rek3(int x, int p){
dp[x][0] = maxn;
dp[x][1] = maxn;
dp[x][2] = maxn;
ll sum = 0;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
rek3(x2, x);
sum += dp[x2][0];
}
if(ovca[x]){
int naj = maxn + 1, y;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(dp[x2][1] - dp[x2][0] < naj){
naj = dp[x2][1] - dp[x2][0];
y = x2;
}
// naj = min(naj, dp[x2][1] - dp[x2][0]);
}
if(naj < 1){
sta[x][0] = y;
}
else {
sta[x][0] = x;
}
dp[x][0] = sum + min(naj, 1);
dp[x][2] = sum;
return;
}
dp[x][0] = min((ll)dp[x][0], sum);
ll sum2 = 0;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(d[x2] + 1 == d[x]) sum2 += dp[x2][2];
else sum2 += dp[x2][0];
}
dp[x][2] = sum2;
if(d[x] <= u[x]){
ll sum3 = 0;
int naj = maxn + 1, y;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(d[x2] + 1 == d[x]){
sum3 += dp[x2][2];
if(dp[x2][1] - dp[x2][2] < naj){
naj = dp[x2][1] - dp[x2][2];
y = x2;
}
// naj = min(naj, dp[x2][1] - dp[x2][2]);
}
else {
sum3 += dp[x2][0];
if(dp[x2][1] - dp[x2][0] < naj){
naj = dp[x2][1] - dp[x2][0];
y = x2;
}
// naj = min(naj, dp[x2][1] - dp[x2][0]);
}
}
if(sum3 + min(naj, 1) < dp[x][0]){
dp[x][0] = sum3 + min(naj, 1);
if(naj < 1) sta[x][0] = y;
else sta[x][0] = x;
}
// dp[x][0] = min((ll)dp[x][0], sum3 + min(naj, 1));
if(d[x] == u[x]){
if(sum3 + min(naj, 1) < dp[x][1]){
dp[x][1] = sum3 + min(naj, 1);
if(naj < 1) sta[x][1] = y;
else sta[x][1] = x;
}
// dp[x][1] = min((ll)dp[x][1], sum3 + min(naj, 1));
}
}
else {
int naj = maxn + 1, y;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(dp[x2][1] - dp[x2][0] < naj){
naj = dp[x2][1] - dp[x2][0];
y = x2;
}
// naj = min(naj, dp[x2][1] - dp[x2][0]);
}
if(sum + min(naj, 1) < dp[x][1]){
dp[x][1] = sum + min(naj, 1);
if(naj < 1) sta[x][1] = y;
else sta[x][1] = x;
}
// dp[x][1] = min((ll)dp[x][1], sum + min(naj, 1));
}
}
void rek4(int x, int p, int b){
// cout << x << ' ' << b << endl;
if(sta[x][b] == x) ans.push_back(x);
if(ovca[x]){
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(sta[x][b] == x2) rek4(x2, x, 1);
else rek4(x2, x, 0);
}
return;
}
if(b == 0 && sta[x][0] == 0){
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
rek4(x2, x, 0);
}
return;
}
if(b == 2){
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(d[x2] + 1 == d[x]) rek4(x2, x, 2);
else rek4(x2, x, 0);
}
return;
}
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
if(x2 == p) continue;
if(sta[x][b] == x2) rek4(x2, x, 1);
else {
if(d[x] <= u[x] && d[x2] + 1 == d[x]) rek4(x2, x, 2);
else rek4(x2, x, 0);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i = 0; i < k; i++){
int a;
cin >> a;
ovca[a] = 1;
}
rek(1, 0);
u[1] = maxn;
rek2(1, 0);
// for(int i = 1; i <= n; i++){
// cout << i << ' ' << u[i] << endl;
// }
rek3(1, 0);
rek4(1, 0, 0);
cout << dp[1][0] << "\n";
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++){
cout << ans[i] << ' ';
}
return 0;
}
Compilation message
pastiri.cpp: In function 'int rek(int, int)':
pastiri.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'int rek2(int, int)':
pastiri.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
62 | }
| ^
pastiri.cpp: In function 'void rek3(int, int)':
pastiri.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'void rek4(int, int, int)':
pastiri.cpp:198:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:210:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:221:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp:233:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
233 | for(int i = 0; i < v[x].size(); i++){
| ~~^~~~~~~~~~~~~
pastiri.cpp: In function 'int main()':
pastiri.cpp:281:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
281 | for(int i = 0; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
278 ms |
213368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
24508 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
370 ms |
72532 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
