Submission #604842

#	Time	Username	Problem	Language	Result	Execution time	Memory
604842		M_W	The Xana coup (BOI21_xanadu)	C++17	10 / 100	79 ms	8988 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
int N;
const int inf = 1000000;
vector<int> adj[100001];
int dp[100001][2][2];
int st[100001];

int main(){
    scanf("%d", &N);
    for(int i = 1, u, v; i < N; i++){
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= N; i++) scanf("%d", &st[i]);
    for(int i = 1; i <= N; i++){
        dp[i][0][0] = dp[i][0][1] = inf;
        dp[i][1][0] = dp[i][1][1] = inf;
    }
    
    dp[2][st[2]][st[1]] = 0; dp[2][1 - st[2]][1 - st[1]] = 1;
    for(int i = 3; i <= N; i++){
        dp[i][st[i]][0] = min(dp[i][st[i]][0], dp[i - 1][0][0]);
        dp[i][st[i]][1] = min(dp[i][st[i]][1], dp[i - 1][1][0]);
        
        dp[i][1 - st[i]][0] = min(dp[i][1 - st[i]][0], dp[i - 1][1][1] + 1);
        dp[i][1 - st[i]][1] = min(dp[i][1 - st[i]][1], dp[i - 1][0][1] + 1);
    }
    dp[N][0][0] = min({dp[N][0][0], dp[N][1][1] + 1});

    if(dp[N][0][0] >= inf) printf("impossible");
    else printf("%d", dp[N][0][0]);
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
xanadu.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
xanadu.cpp:16:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     for(int i = 1; i <= N; i++) scanf("%d", &st[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~

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