Submission #962045

#	Time	Username	Problem	Language	Result	Execution time	Memory
962045		phoenix0423	The Xana coup (BOI21_xanadu)	C++17	100 / 100	73 ms	34640 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
const int INF = 1e9;
vector<int> adj[maxn];
int a[maxn], dp[maxn][2][2];
int n;

void dfs(int pos, int prev){
    if(prev != -1) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
    for(auto x : adj[pos]){
        dfs(x, pos);
    }
    for(int j = 0; j < 2; j++){
        for(int k = 0; k < 2; k++){
            //calculate dp[pos][j][k];
            vector<int> dif;
            int sum = 0;
            for(auto x : adj[pos]){
                sum += dp[x][0][j];
                dif.pb(dp[x][1][j] - dp[x][0][j]);
            }
            sort(dif.begin(), dif.end());
            int nd = (a[pos] + j + k) % 2;
            dp[pos][j][k] = INF;
            if(nd == 0) dp[pos][j][k] = sum;
            for(int i = 0; i < dif.size(); i++){
                sum += dif[i];
                if((i + 1) % 2 == nd) dp[pos][j][k] = min(dp[pos][j][k], sum);
            }
            if(j) dp[pos][j][k] += 1;
        }
    }
}
signed main(void){
    fastio;
    cin>>n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i = 0; i < n; i++) cin>>a[i];
    dfs(0, -1);
    int ans = min(dp[0][0][0], dp[0][1][0]);
    if(ans < INF) cout<<ans<<"\n";
    else cout<<"impossible\n";
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:35:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int i = 0; i < dif.size(); i++){
      |                            ~~^~~~~~~~~~~~

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