Submission #429574

#	Time	Username	Problem	Language	Result	Execution time	Memory
429574		giorgikob	The Xana coup (BOI21_xanadu)	C++14	100 / 100	120 ms	24740 KiB

xanadu

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e5+50, mod = 998244353, K = 31;

int dp[N][2][2][2];
int n;
int A[N];
vector<int>gr[N];
int x,y;
///// chartuli, dawerili, shvilebi;

inline void Min(int &x,int val){
    x = min(x,val);
}

void dfs(int x,int p){

    int cur = A[x];

    if(x != 1 && gr[x].size() == 1){
        dp[x][cur][0][0] = 0;
        dp[x][1-cur][1][0] = 1;
        dp[x][cur][0][1] = 0;
        dp[x][1-cur][1][1] = 1;
        return ;
    }

    dp[x][cur][0][0] = 0;
    dp[x][cur][0][1] = 0;

    for(auto to : gr[x]){
        if(to == p) continue;
        dfs(to,x);
        int cur_dp[2][2][2];
        for(int j = 0; j < 2; j++){
            for(int t = 0; t < 2; t++){
                for(int k = 0; k < 2; k++){
                    cur_dp[j][t][k] = 1e9;
                }
            }
        }

        for(int chart = 0; chart < 2; chart++){
            //for(int daw = 0; daw < 2; daw++){
            int daw = 0;
                for(int shvi = 0; shvi < 2; shvi++){
                    if(dp[x][chart][daw][shvi] >= 1e9) continue;
                    int res = dp[x][chart][daw][shvi];
                    Min(cur_dp[chart][daw][shvi], res+dp[to][shvi][0][0]);
                    Min(cur_dp[1-chart][daw][shvi], res+dp[to][shvi][1][0]);
                }
            //}
        }

        for(int j = 0; j < 2; j++){
            for(int t = 0; t < 2; t++){
                for(int k = 0; k < 2; k++){
                    dp[x][j][t][k] = cur_dp[j][t][k];
                }
            }
        }


    }
    Min(dp[x][0][1][0], dp[x][1][0][1]+1);
    Min(dp[x][1][1][0], dp[x][0][0][1]+1);
}

inline void test_case(){
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        gr[x].pb(y);
        gr[y].pb(x);
    }

    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 2; j++){
            for(int t = 0; t < 2; t++){
                for(int k = 0; k < 2; k++){
                    dp[i][j][t][k] = 1e9;
                }
            }
        }
    }

    dfs(1,0);

    int answer = min(dp[1][0][0][0],dp[1][0][1][0]);

    if(answer >= 1e9){
        cout << "impossible" << endl;
    } else {
        cout << answer << endl;
    }
}
 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    for(int i = 1; i <= T; i++){
        test_case();
    }
}

Compilation message (stderr)

xanadu.cpp:106:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 |  main(){
      |  ^~~~

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