Submission #566462

#	Time	Username	Problem	Language	Result	Execution time	Memory
566462		Waratpp123	The Xana coup (BOI21_xanadu)	C++14	100 / 100	107 ms	28332 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
vector<long long> g[100010];
long long st[100010],dp[100010][2][2];
void dfs(long long i,long long p){
    for(auto x : g[i]){
        if(x==p) continue;
        dfs(x,i);
    }
    vector<long long> u,v;
    long long sum=0,j;
    //press dp[i][0][?]
    for(auto x : g[i]){
        if(x==p) continue;
        u.push_back(dp[x][1][1]-dp[x][0][1]);
        sum=sum+1ll*dp[x][0][1];
    }
    sort(u.begin(),u.end());
    for(j=1;j<u.size();j++){
        u[j]+=u[j-1];
    }
    if(st[i]==0){
        dp[i][1][1]=min(dp[i][1][1],1+sum);
    }else{
        dp[i][1][0]=min(dp[i][1][1],1+sum);
    }
    for(j=0;j<u.size();j++){
        if(j%2==st[i]){
            dp[i][1][0]=min(dp[i][1][0],1+sum+u[j]);
        }else{
            dp[i][1][1]=min(dp[i][1][1],1+sum+u[j]);
        }
    }
    u.clear();
    //notpress dp[i][0][?]
    sum=0;
     for(auto x : g[i]){
        if(x==p) continue;
        u.push_back(dp[x][1][0]-dp[x][0][0]);
        sum=sum+1ll*dp[x][0][0];
    }
    sort(u.begin(),u.end());
    for(j=1;j<u.size();j++){
        u[j]+=u[j-1];
    }
    if(st[i]==0){
        dp[i][0][0]=min(dp[i][0][0],sum);
    }else{
        dp[i][0][1]=min(dp[i][0][0],sum);
    }
    for(j=0;j<u.size();j++){
        if(j%2!=st[i]){
            dp[i][0][0]=min(dp[i][0][0],sum+u[j]);
        }else{
            dp[i][0][1]=min(dp[i][0][1],sum+u[j]);
        }
    }
}
int main(){
    long long i,n,u,v;
    scanf("%lld",&n);
    for(i=1;i<=n-1;i++){
        scanf("%lld %lld",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(i=1;i<=n;i++) scanf("%lld",&st[i]),dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=1000000000;
    dfs(1,-1);
    if(min(dp[1][1][0],dp[1][0][0])>n) printf("impossible\n");
    else printf("%lld",min(dp[1][1][0],dp[1][0][0]));
return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:19:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(j=1;j<u.size();j++){
      |             ~^~~~~~~~~
xanadu.cpp:27:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(j=0;j<u.size();j++){
      |             ~^~~~~~~~~
xanadu.cpp:43:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(j=1;j<u.size();j++){
      |             ~^~~~~~~~~
xanadu.cpp:51:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(j=0;j<u.size();j++){
      |             ~^~~~~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
xanadu.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%lld %lld",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
xanadu.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     for(i=1;i<=n;i++) scanf("%lld",&st[i]),dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=1000000000;
      |                       ~~~~~^~~~~~~~~~~~~~~

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