Submission #484874

#	Time	Username	Problem	Language	Result	Execution time	Memory
484874		ETK	The Xana coup (BOI21_xanadu)	C++14	100 / 100	90 ms	38080 KiB

xanadu

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=1e6+5;
int n,f[N][2][2],C[N];//节点，是否操作，颜色
vector <int> G[N];
void dfs(int u,int fa){
    rep(i,0,1){
        f[u][i][C[u]^i]=i;
        f[u][i][C[u]^i^1]=n+1;
    }
    for(int v:G[u])if(v!=fa){
        dfs(v,u);
        rep(i,0,1){
            int f0=f[u][i][0],f1=f[u][i][1];
            f[u][i][0]=min(n+1,min(f0+f[v][0][i],f1+f[v][1][i]));
            f[u][i][1]=min(n+1,min(f0+f[v][1][i],f1+f[v][0][i]));
        }
    }
}
int main(){
    scanf("%d",&n);
    rep(i,2,n){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    rep(i,1,n)scanf("%d",&C[i]);
    dfs(1,0);
    int ans=min(f[1][0][0],f[1][1][0]);
    if(ans>n)puts("impossible");
    else printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
xanadu.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
xanadu.cpp:28:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     rep(i,1,n)scanf("%d",&C[i]);
      |               ~~~~~^~~~~~~~~~~~

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