Submission #315975

#TimeUsernameProblemLanguageResultExecution timeMemory
315975ahmetPastiri (COI20_pastiri)C++14
0 / 100
615 ms74272 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...