Submission #430035

#	Time	Username	Problem	Language	Result	Execution time	Memory
430035		lukameladze	The Xana coup (BOI21_xanadu)	C++14	100 / 100	188 ms	24512 KiB

xanadu

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
long long dp1[5],dp[3][3][N],x,xx,xx1,c[N],n,a,b;
vector <long long> vv,v[N];
pair <long long, long long> pp;
pair <long long, long long> go(int col, int a, int p) {
     dp1[0]=0; dp1[1]=1e9;
     for (int i=0; i<v[a].size(); i++) {
          if (v[a][i]==p) continue;
          x=v[a][i]; xx=dp1[0]; xx1=dp1[1];
          dp1[0]=min(xx+dp[col][0][x], xx1+dp[col][1][x]);
          dp1[1]=min(xx1+dp[col][0][x], xx+dp[col][1][x]);
     }
     return {dp1[0], dp1[1]};
}
void dfs(int a, int p) {
     vv.clear();
     for (int i=0; i<v[a].size(); i++) {
          if (v[a][i]!=p) dfs(v[a][i],a);
     }
     for (int i=0; i<v[a].size(); i++) {
          if (v[a][i]!=p) vv.pb(v[a][i]);
     }
     //dp[0][0][a], dp[1][0][a]
     pp=go(0,a,p);
     if (c[a]==0)
     dp[0][0][a]=pp.f; else dp[0][0][a]=pp.s;
     if (c[a]==0) dp[1][0][a]=pp.s; else dp[1][0][a]=pp.f;
     // dp[0][1][a] dp[1][1][a]
     pp=go(1,a,p);
     //if (a==4 || a==5) cout<<a<<endl;
     //if (a==4) cout<<pp.f<<" "<<pp.s<<endl;
     if (c[a]==0) dp[0][1][a]=pp.s+1; else dp[0][1][a]=pp.f+1;
     if (c[a]==0) dp[1][1][a]=pp.f+1; else dp[1][1][a]=pp.s+1;
}
int main() {
     cin>>n;
     for (int i=1; i<=n-1; i++) {
          cin>>a>>b;
          v[a].pb(b); v[b].pb(a);
     }
     for (int i=1; i<=n; i++) {
          cin>>c[i];
     }
     dfs(1,0);
    // cout<<dp[0][1][5]<<endl;
    if (min(dp[0][1][1],dp[0][0][1])>=1e9) cout<<"impossible"<<endl;
    else
      cout<<min(dp[0][1][1],dp[0][0][1])<<endl;
}

Compilation message (stderr)

xanadu.cpp: In function 'std::pair<long long int, long long int> go(int, int, int)':
xanadu.cpp:12:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |      for (int i=0; i<v[a].size(); i++) {
      |                    ~^~~~~~~~~~~~
xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |      for (int i=0; i<v[a].size(); i++) {
      |                    ~^~~~~~~~~~~~
xanadu.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |      for (int i=0; i<v[a].size(); i++) {
      |                    ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30