Submission #426171

#	Time	Username	Problem	Language	Result	Execution time	Memory
426171		duality	The Xana coup (BOI21_xanadu)	C++11	100 / 100	114 ms	15304 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

vi adjList[100000];
int c[100000];
int dp[100000][2][2],temp[2][2],temp2[2][2];
int doDFS(int u,int p) {
    int i;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) doDFS(v,u);
    }
    temp[0][c[u]] = 0,temp[1][c[u]^1] = 1;
    temp[0][c[u]^1] = temp[1][c[u]] = 1e9;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) {
            temp2[0][0] = min(temp[0][0]+dp[v][0][0],temp[0][1]+dp[v][1][0]);
            temp2[0][1] = min(temp[0][1]+dp[v][0][0],temp[0][0]+dp[v][1][0]);
            temp2[1][0] = min(temp[1][0]+dp[v][0][1],temp[1][1]+dp[v][1][1]);
            temp2[1][1] = min(temp[1][1]+dp[v][0][1],temp[1][0]+dp[v][1][1]);
            temp[0][0] = min(temp2[0][0],(int) 1e9);
            temp[0][1] = min(temp2[0][1],(int) 1e9);
            temp[1][0] = min(temp2[1][0],(int) 1e9);
            temp[1][1] = min(temp2[1][1],(int) 1e9);
        }
    }
    dp[u][0][0] = temp[0][0];
    dp[u][0][1] = temp[0][1];
    dp[u][1][0] = temp[1][0];
    dp[u][1][1] = temp[1][1];
    return 0;
}
int main() {
    int i;
    int N,a,b;
    scanf("%d",&N);
    for (i = 0; i < N-1; i++) {
        scanf("%d %d",&a,&b);
        a--,b--;
        adjList[a].pb(b);
        adjList[b].pb(a);
    }
    for (i = 0; i < N; i++) scanf("%d",&c[i]);
    doDFS(0,-1);
    if (min(dp[0][0][0],dp[0][1][0]) >= 1e9) printf("impossible\n");
    else printf("%d\n",min(dp[0][0][0],dp[0][1][0]));

    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'int doDFS(int, int)':
xanadu.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
xanadu.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
xanadu.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
xanadu.cpp:50:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     for (i = 0; i < N; i++) scanf("%d",&c[i]);
      |                             ~~~~~^~~~~~~~~~~~

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