oj.uz

Submission #404645

# Submission time Handle Problem Language Result Execution time Memory
404645 2021-05-14T19:17:49 Z nicolaalexandra The Xana coup (BOI21_xanadu) C++14
30 / 100
 146 ms 13920 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 10000000
using namespace std;

int dp[DIM][2][2],v[DIM];
vector <int> L[DIM];
int n,i,x,y;

void dfs (int nod, int tata){
    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
        }
    if (!ok){
        dp[nod][v[nod]][0] = 0;
        dp[nod][1-v[nod]][1] = 1;
    } else {

        /// caz 1: nu dau switch in nod
        int sum = 0, cnt = 0;
        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            if (dp[vecin][0][0] < dp[vecin][0][1])
                sum += dp[vecin][0][0];
            else {
                sum += dp[vecin][0][1];
                cnt++;
            }
        }

        if (cnt % 2 == 0)
            dp[nod][v[nod]][0] = sum;
        else dp[nod][1-v[nod]][0] = sum;

        /// incerc sa schimb paritatea lui cnt
        int mini = INF;
        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            if (dp[vecin][0][0] < dp[vecin][0][1])
                mini = min (mini,sum - dp[vecin][0][0] + dp[vecin][0][1]);
            else mini = min (mini,sum - dp[vecin][0][1] + dp[vecin][0][0]);
        }

        if (cnt % 2 == 0)
            dp[nod][1-v[nod]][0] = mini;
        else dp[nod][v[nod]][0] = mini;


        /// caz 2: dau switch in nod
        cnt = 1, sum = 0;
        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            if (dp[vecin][1][0] < dp[vecin][1][1])
                sum += dp[vecin][1][0];
            else {
                sum += dp[vecin][1][1];
                cnt++;
            }
        }

        if (cnt % 2 == 0)
            dp[nod][v[nod]][1] = 1 + sum;
        else dp[nod][1-v[nod]][1] = 1 + sum;

        /// schimb starea din nod
        mini = INF;
        for (auto vecin : L[nod]){
            if (vecin == tata)
                continue;
            if (dp[vecin][1][0] < dp[vecin][1][1])
                mini = min (mini,sum - dp[vecin][1][0] + dp[vecin][1][1]);
            else mini = min (mini, sum - dp[vecin][1][1] + dp[vecin][1][0]);
        }

        if (cnt % 2 == 0)
            dp[nod][1-v[nod]][1] = 1 + mini;
        else dp[nod][v[nod]][1] = 1 + mini;

    }
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (i=1;i<=n;i++){
        cin>>v[i];
        dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = INF;
    }

    dfs (1,0);

    int sol = min(dp[1][0][0],dp[1][0][1]);
    if (sol == INF)
        cout<<"impossible";
    else cout<<sol;


    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2656 KB Output is correct
7 Correct 2 ms 2660 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2656 KB Output is correct
13 Correct 2 ms 2656 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 13884 KB Output is correct
2 Correct 113 ms 13760 KB Output is correct
3 Correct 115 ms 13860 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 13920 KB Output is correct
2 Correct 115 ms 13760 KB Output is correct
3 Correct 146 ms 13876 KB Output is correct
4 Correct 112 ms 7164 KB Output is correct
5 Incorrect 119 ms 8836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2656 KB Output is correct
7 Correct 2 ms 2660 KB Output is correct
8 Correct 3 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2656 KB Output is correct
13 Correct 2 ms 2656 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 113 ms 13884 KB Output is correct
18 Correct 113 ms 13760 KB Output is correct
19 Correct 115 ms 13860 KB Output is correct
20 Correct 124 ms 13920 KB Output is correct
21 Correct 115 ms 13760 KB Output is correct
22 Correct 146 ms 13876 KB Output is correct
23 Correct 112 ms 7164 KB Output is correct
24 Incorrect 119 ms 8836 KB Output isn't correct
25 Halted 0 ms 0 KB -