| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 315975 |
2020-10-24T16:07:57 Z |
ahmet |
Pastiri (COI20_pastiri) |
C++14 |
|
615 ms |
74272 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int mx=2e6+5;
int n,k;
vector <int> v[mx];
vector <int> a;
unordered_set <int> s;
int cl[mx];
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
/*freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
*/
cin >> n >> k;
rep(i,n-1){
int x,y;cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
cl[i]=100000000;
}
cl[n]=cl[n-1]=100000000;
rep(i,k){
int x;cin >> x;
a.pb(x);
}
queue <pair < int,pair <int, int> > >q;
for(int i=0;i<a.size();++i){
cl[a[i]]=0;
}
for(int i=0;i<a.size();++i){
for(int j=0;j<v[a[i]].size();++j){
if(cl[v[a[i]][j]]!=100000000){s.insert(a[i]);}
else {q.push(mp(1,mp(v[a[i]][j],a[i])));}
}
}
while(!q.empty()){
int val=q.front().first;
int cur=q.front().second.first;
int par=q.front().second.second;
q.pop();
if(cl[cur]<val){
s.insert(par);
continue;
}
cl[cur]=val;
int say=0;
for(int i=0;i<v[cur].size();++i){
int nxt=v[cur][i];
if(nxt!=par and cl[nxt]>=val+1){q.push(mp(val+1,mp(nxt,cur)));++say;}
}
if(say==0)s.insert(cur);
}
cout << s.size() << endl;
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
// cout << cl[1] <<cl[2] << cl[3] << cl[4] << endl;
}
/*
4 2
1 2
2 3
3 4
1 4
*/
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
| ^
pastiri.cpp:23:2: note: in expansion of macro 'rep'
23 | rep(i,n-1){
| ^~~
pastiri.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
| ^
pastiri.cpp:30:2: note: in expansion of macro 'rep'
30 | rep(i,k){
| ^~~
pastiri.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<a.size();++i){
| ~^~~~~~~~~
pastiri.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<a.size();++i){
| ~^~~~~~~~~
pastiri.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j=0;j<v[a[i]].size();++j){
| ~^~~~~~~~~~~~~~~
pastiri.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<v[cur].size();++i){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
65016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
47608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
47488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
615 ms |
74272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
