Submission #1105530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105530		andrewp	The Xana coup (BOI21_xanadu)	C++14	100 / 100	51 ms	16968 KiB

xanadu

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h>      
using namespace std;  
using ll=int64_t; 
using pii=pair<int,int>;
using pll=pair<int,int>;    
#define pb push_back
#define fi first
#define se second
#define mp make_pair 
#define ldb double
#define all(x) x.begin(),x.end()
#define raint(x) x.rbegin(),x.rend()     
void rd(int&x){scanf("%d",&x);}
void rd(ll&x){scanf("%lld",&x);}
void rd(char*x){scanf("%s",x);}
void rd(ldb&x){scanf("%lf",&x);}
void rd(string&x){scanf("%s",&x);}
int ri(){int x;rd(x);return x;}  
// #ifndef ONLINE_JUDGE
// #include "C:\Users\andre\Downloads\cpp-dump-0.7.0\cpp-dump-0.7.0\cpp-dump.hpp" 
// #define dbg(...) cpp_dump(__VA_ARGS__)
// #else
// #define dump(...)
// #endif  
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&i:x)rd(i);}
template<typename T,typename...A>void rd(T&x,A&...args){rd(x);rd(args...);}
template<typename T>void rd(){T x;rd(x);return x;} 
template<typename T>vector<T> rv(int n){vector<T> x(n);rd(x);return x;} 
const int N=1e5+50;  
int n,a[N],dp[N][2][2];
vector<int> G[N];
void dfs(int x,int par){
    if(!a[x]){
        dp[x][0][1]=dp[x][1][0]=N;
        dp[x][0][0]=0;
        dp[x][1][1]=1;
    }else{
        dp[x][0][0]=dp[x][1][1]=N;
        dp[x][0][1]=1;
        dp[x][1][0]=0;
    }
    for(int u:G[x]){
        if(u!=par){
            dfs(u,x);
            for(int k=0;k<2;k++){
                int f=dp[x][0][k],s=dp[x][1][k];
                dp[x][0][k]=min(dp[u][k][0]+f,dp[u][k][1]+s);
                dp[x][1][k]=min(dp[u][k][1]+f,dp[u][k][0]+s);
            }
        }
    }
}
int main(){
    n=ri();
    for(int i=1;i<n;i++){
        int u,v; rd(u,v);
        G[u].pb(v);
        G[v].pb(u);
    }
    for(int i=1;i<=n;i++) a[i]=ri();
    dfs(1,1);
    int ans=min(dp[1][0][0],dp[1][0][1]);
    if(ans>n) printf("impossible\n");
    else printf("%d\n",ans);
    return 0;   
}   

Compilation message (stderr)

xanadu.cpp: In function 'void rd(ll&)':
xanadu.cpp:16:25: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka 'long int*'} [-Wformat=]
   16 | void rd(ll&x){scanf("%lld",&x);}
      |                      ~~~^  ~~
      |                         |  |
      |                         |  ll* {aka long int*}
      |                         long long int*
      |                      %ld
xanadu.cpp: In function 'void rd(std::string&)':
xanadu.cpp:19:27: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'std::string*' {aka 'std::__cxx11::basic_string<char>*'} [-Wformat=]
   19 | void rd(string&x){scanf("%s",&x);}
      |                          ~^  ~~
      |                           |  |
      |                           |  std::string* {aka std::__cxx11::basic_string<char>*}
      |                           char*
xanadu.cpp: In function 'void rd(int&)':
xanadu.cpp:15:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void rd(int&x){scanf("%d",&x);}
      |                ~~~~~^~~~~~~~~
xanadu.cpp: In function 'void rd(ll&)':
xanadu.cpp:16:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | void rd(ll&x){scanf("%lld",&x);}
      |               ~~~~~^~~~~~~~~~~
xanadu.cpp: In function 'void rd(char*)':
xanadu.cpp:17:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void rd(char*x){scanf("%s",x);}
      |                 ~~~~~^~~~~~~~
xanadu.cpp: In function 'void rd(double&)':
xanadu.cpp:18:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | void rd(ldb&x){scanf("%lf",&x);}
      |                ~~~~~^~~~~~~~~~
xanadu.cpp: In function 'void rd(std::string&)':
xanadu.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void rd(string&x){scanf("%s",&x);}
      |                   ~~~~~^~~~~~~~~

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