Submission #782929

#	Time	Username	Problem	Language	Result	Execution time	Memory
782929		christinelynn	The Xana coup (BOI21_xanadu)	C++17	5 / 100	1096 ms	7252 KiB

xanadu

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
  LL n;
  scanf("%lld",&n);
  vector<LL>adj[n+5];  
  for(LL a=1;a<=n-1;a++)
  {
    LL x,y;
    scanf("%lld %lld",&x,&y);
    x--,y--;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  LL deg[n+5];
  for(LL a=0;a<n;a++)scanf("%lld",&deg[a]);
  LL minn=1e9;
  for(LL a=0;a<(1LL<<n);a++)
  {
    LL temp[n+5];
    for(LL b=0;b<n;b++)temp[b]=deg[b];
  //  if(a==4)cout<<"a="<<a<<endl;
    for(LL x=0;x<n;x++)
    {
      if(a&(1<<x))
      {
      //  cout<<temp[x]<<endl;
        temp[x]=temp[x]^1;
      //  cout<<temp[x]<<endl;
        for(LL jeje:adj[x])
        {
          temp[jeje]=temp[jeje]^1;
    //      if(a==4)printf("temp[%lld]=%lld\n",jeje,temp[jeje]);
        }
    //    if(a==4)
    //    {
    //      printf("x = ");
    //      cout<<x<<endl;
    //      for(LL b=0;b<n;b++)cout<<deg[b]<<" ";
    //      cout<<endl;
    //    }
      }
    }
    bool jawab=1;
    for(LL b=0;b<n;b++)
    {
      if(temp[b]==1)
      {
        jawab=0;
        break;
      }
    }
    if(jawab)
    {
  //    printf("a = %lld\n",a);
      if(__builtin_popcount(a)<minn)
      {
        minn=__builtin_popcount(a);
      }
    }
  }
  if(minn==1e9)cout<<"impossible"<<endl;
  else cout<<minn<<endl;
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:7:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |   scanf("%lld",&n);
      |   ~~~~~^~~~~~~~~~~
xanadu.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%lld %lld",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
xanadu.cpp:18:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   for(LL a=0;a<n;a++)scanf("%lld",&deg[a]);
      |                      ~~~~~^~~~~~~~~~~~~~~~

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