Submission #578248

#TimeUsernameProblemLanguageResultExecution timeMemory
578248juggernautSpring cleaning (CEOI20_cleaning)C++14
34 / 100
1090 ms25096 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif vector<int>g[200005]; ll dp[200005][2]; void dfs(int v,int p){ for(int to:g[v])if(to^p)dfs(to,v); if(g[v].size()==1&&p){ dp[v][0]=1e15; dp[v][1]=0; return; } dp[v][0]=dp[v][1]=0; vector<pair<ll,int>>vec; for(int to:g[v])if(to^p)vec.push_back(make_pair(dp[to][1]-dp[to][0],to)); sort(vec.begin(),vec.end()); { dp[v][1]+=dp[vec[0].sc][1]+1; for(int i=1;i<(int)vec.size();i++){ if(i+1<(int)vec.size()){ dp[v][1]+=min(dp[vec[i].sc][0]+dp[vec[i+1].sc][0]+4,dp[vec[i].sc][1]+dp[vec[i+1].sc][1]+2); i++; }else dp[v][1]+=dp[vec[i].sc][0]+2; } } { for(int i=0;i<(int)vec.size();i++){ if(i+1<(int)vec.size()){ dp[v][0]+=min(dp[vec[i].sc][0]+dp[vec[i+1].sc][0]+4,dp[vec[i].sc][1]+dp[vec[i+1].sc][1]+2); i++; }else dp[v][0]+=dp[vec[i].sc][0]+2; } } } int main(){ int n,q; scanf("%d%d",&n,&q); for(int i=1;i^n;i++){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs(1,0); if(true){ if(__builtin_popcount(n+1)==1){ while(q--){ int m; scanf("%d",&m); int leaf=0; int cnt=0; while(m--){ int x; scanf("%d",&x); if(g[x].size()==1)leaf++; else cnt++; } if(cnt&1)puts("-1"); else printf("%lld\n",dp[1][0]+cnt+leaf); } return 0; } } while(q--){ int m; scanf("%d",&m); vector<int>vec; int timer=n+1; while(m--){ int x; scanf("%d",&x); vec.push_back(x); g[x].push_back(timer); g[timer].push_back(x); timer++; } dfs(1,0); ll ans=dp[1][g[1].size()==1]; if(ans>=(1e15))ans=-1; printf("%lld\n",ans); timer=n+1; for(int &x:vec){ g[x].pop_back(); g[timer].clear(); timer++; } } }

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
cleaning.cpp:70:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |      scanf("%d",&x);
      |      ~~~~~^~~~~~~~~
cleaning.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d",&m);
      |   ~~~~~^~~~~~~~~
cleaning.cpp:87:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...