oj.uz

Submission #769408

# Submission time Handle Problem Language Result Execution time Memory
769408 2023-06-29T14:13:52 Z raysh07 The Xana coup (BOI21_xanadu) C++17
100 / 100
 50 ms 18840 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 69;
int dp[N][2][2], a[N], n, ndp[2][2];
vector <int> adj[N];

void dfs(int u, int par = -1){
    //second index --> is subtree head off 
    //third index --> did you use operation at subtree head 
    
    dp[u][a[u]][0] = 0;
    dp[u][a[u] ^ 1][1] = 1;
    
    for (int v : adj[u]){
        if (v != par){
            dfs(v, u);
            ndp[0][0] = ndp[0][1] = ndp[1][0] = ndp[1][1] = INF;
            for (int s = 0; s < 2; s++){
                //current state of head 
                for (int op = 0; op < 2; op++){
                    //used op at current head or not 
                    for (int op1 = 0; op1 < 2; op1++){
                        //used op at child or not 
                        int need = op;
                        
                        ndp[s ^ op1][op] = min(ndp[s ^ op1][op], dp[u][s][op] + dp[v][need][op1]);
                    }
                }
            }
            
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 2; j++){
                    dp[u][i][j] = ndp[i][j];
                }
            }
        }
    }
    
    // cout << u << "\n";
    // for (int i = 0; i < 2; i++){
    //     for (int j = 0; j < 2; j++){
    //         cout << dp[u][i][j] << " ";
    //     }
    // }
    // cout << "\n";
}

void Solve() 
{
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 0; i < N; i++){
        for (int j = 0; j < 2; j++){
            for (int k = 0; k < 2; k++){
                dp[i][j][k] = INF;
            }
        }
    }
    
    dfs(1);
    
    int ans = INF;
    for (int i = 0; i < 1; i++){
        for (int j = 0; j < 2; j++){
            ans = min(ans, dp[1][i][j]);
        }
    }
    
    if (ans == INF) cout << "impossible\n";
    else cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5732 KB Output is correct
2 Correct 3 ms 5752 KB Output is correct
3 Correct 3 ms 5752 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5732 KB Output is correct
2 Correct 3 ms 5752 KB Output is correct
3 Correct 3 ms 5752 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 4 ms 5760 KB Output is correct
7 Correct 2 ms 5716 KB Output is correct
8 Correct 2 ms 5716 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 2 ms 5716 KB Output is correct
15 Correct 2 ms 5716 KB Output is correct
16 Correct 3 ms 5760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 18784 KB Output is correct
2 Correct 37 ms 18556 KB Output is correct
3 Correct 35 ms 18768 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 18728 KB Output is correct
2 Correct 48 ms 18612 KB Output is correct
3 Correct 36 ms 18764 KB Output is correct
4 Correct 33 ms 11280 KB Output is correct
5 Correct 39 ms 11720 KB Output is correct
6 Correct 36 ms 11900 KB Output is correct
7 Correct 3 ms 5756 KB Output is correct
8 Correct 14 ms 7764 KB Output is correct
9 Correct 50 ms 11564 KB Output is correct
10 Correct 43 ms 11652 KB Output is correct
11 Correct 35 ms 11920 KB Output is correct
12 Correct 37 ms 12236 KB Output is correct
13 Correct 38 ms 11828 KB Output is correct
14 Correct 43 ms 12144 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5732 KB Output is correct
2 Correct 3 ms 5752 KB Output is correct
3 Correct 3 ms 5752 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 4 ms 5760 KB Output is correct
7 Correct 2 ms 5716 KB Output is correct
8 Correct 2 ms 5716 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 3 ms 5716 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 3 ms 5716 KB Output is correct
14 Correct 2 ms 5716 KB Output is correct
15 Correct 2 ms 5716 KB Output is correct
16 Correct 3 ms 5760 KB Output is correct
17 Correct 47 ms 18784 KB Output is correct
18 Correct 37 ms 18556 KB Output is correct
19 Correct 35 ms 18768 KB Output is correct
20 Correct 46 ms 18728 KB Output is correct
21 Correct 48 ms 18612 KB Output is correct
22 Correct 36 ms 18764 KB Output is correct
23 Correct 33 ms 11280 KB Output is correct
24 Correct 39 ms 11720 KB Output is correct
25 Correct 36 ms 11900 KB Output is correct
26 Correct 3 ms 5756 KB Output is correct
27 Correct 14 ms 7764 KB Output is correct
28 Correct 50 ms 11564 KB Output is correct
29 Correct 43 ms 11652 KB Output is correct
30 Correct 35 ms 11920 KB Output is correct
31 Correct 37 ms 12236 KB Output is correct
32 Correct 38 ms 11828 KB Output is correct
33 Correct 43 ms 12144 KB Output is correct
34 Correct 3 ms 5716 KB Output is correct
35 Correct 3 ms 5716 KB Output is correct
36 Correct 3 ms 5716 KB Output is correct
37 Correct 3 ms 5716 KB Output is correct
38 Correct 3 ms 5716 KB Output is correct
39 Correct 3 ms 5716 KB Output is correct
40 Correct 3 ms 5756 KB Output is correct
41 Correct 2 ms 5716 KB Output is correct
42 Correct 3 ms 5716 KB Output is correct
43 Correct 3 ms 5716 KB Output is correct
44 Correct 3 ms 5716 KB Output is correct
45 Correct 36 ms 18764 KB Output is correct
46 Correct 35 ms 18580 KB Output is correct
47 Correct 43 ms 18840 KB Output is correct
48 Correct 45 ms 11276 KB Output is correct
49 Correct 45 ms 11824 KB Output is correct
50 Correct 37 ms 11904 KB Output is correct
51 Correct 3 ms 5844 KB Output is correct
52 Correct 14 ms 7744 KB Output is correct
53 Correct 34 ms 11544 KB Output is correct
54 Correct 35 ms 11644 KB Output is correct
55 Correct 36 ms 11984 KB Output is correct
56 Correct 41 ms 12144 KB Output is correct
57 Correct 34 ms 11744 KB Output is correct
58 Correct 38 ms 12180 KB Output is correct
59 Correct 13 ms 7732 KB Output is correct
60 Correct 38 ms 10976 KB Output is correct
61 Correct 34 ms 11416 KB Output is correct
62 Correct 36 ms 11628 KB Output is correct
63 Correct 36 ms 11596 KB Output is correct
64 Correct 35 ms 11624 KB Output is correct
65 Correct 32 ms 12068 KB Output is correct
66 Correct 33 ms 12012 KB Output is correct
67 Correct 29 ms 11784 KB Output is correct
68 Correct 28 ms 11840 KB Output is correct
69 Correct 28 ms 11776 KB Output is correct
70 Correct 39 ms 12076 KB Output is correct