Submission #551024

#TimeUsernameProblemLanguageResultExecution timeMemory
551024ivan24The Xana coup (BOI21_xanadu)C++14
0 / 100
3 ms468 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long int; typedef vector<ll> vi; typedef pair<ll,ll> ii; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; #define F first #define S second ll min(ll x, ll y){ return ((x < y) ? x : y); } ll max (ll x, ll y){ return ((x > y) ? x : y); } ll n; vvi adjList; vi on,p; ll dp[2][2][100000]; const ll INF = 1e9; // dp[works][isOn][node] void dfs (ll v){ for (auto u: adjList[v]){ if (p[v] == u) continue; dfs(u); } for (ll isOn = 0; 2 > isOn; isOn++){ ll ctr = 0, sum = 0; bool bawal = false; for (auto u: adjList[v]){ if (p[v] == u) continue; if (dp[1-isOn][0][u] != INF){ sum += dp[1-isOn][0][u]; }else if (dp[1-isOn][1][u] != INF){ sum += dp[1-isOn][1][u]; ctr++; }else if (dp[1-isOn][1][u] == INF && dp[1-isOn][0][u] == INF){ bawal = true; //cout << u << endl; }else{ throw("lol\n"); } } if (bawal) continue; ctr %= 2; ll works = (ctr+on[v]+isOn)%2; dp[works][isOn][v] = sum+isOn; } } void set_p(ll v){ for (auto u: adjList[v]){ if (p[v] == u) continue; p[u] = v; set_p(u); } for (ll i = 0; 4 > i; i++) dp[i/2][i%2][v] = INF; } int main(){ throw("lol\n"); cin >> n; adjList.resize(n); for (ll i = 0; n-1 > i; i++){ ll u,v; cin >> u >> v; u--; v--; adjList[u].push_back(v); adjList[v].push_back(u); } on.resize(n); for (auto &i: on){ cin >> i; i = 1-i; } p.assign(n,-1); set_p(0); dfs(0); /* for (ll v = 0; n > v; v++){ for (ll i = 0; 2 > i; i++){ for (ll j = 0; 2 > j; j++) cout << dp[i][j][v] << " "; } cout << "\n"; } */ ll res = min(dp[1][1][0], dp[1][0][0]); if (res == INF) cout << "impossible\n"; else cout << res << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...