oj.uz

Submission #601290

# Submission time Handle Problem Language Result Execution time Memory
601290 2022-07-21T15:27:29 Z alexander707070 The Xana coup (BOI21_xanadu) C++14
100 / 100
 347 ms 75508 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

int n,a,b,c[MAXN];
vector<int> v[MAXN];

vector<int> sp[MAXN][2][2];
vector<bool> us[MAXN][2][2];

int dp[MAXN][2][2],ans;
bool li[MAXN][2][2];

int ff(int x,int p,int fx,int fp);
int ff2(int x,int p,int ost,int d,int id);

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        for(int f=0;f<2;f++){
            for(int k=0;k<2;k++){
                sp[a][f][k].push_back(0); sp[b][f][k].push_back(0);
                us[a][f][k].push_back(false); us[b][f][k].push_back(false);
            }
        }
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }

    ans=min(ff(1,0,0,0),ff(1,0,1,0)+1);

    if(ans>=1000000){
        cout<<"impossible\n";
    }else{
        cout<<ans<<"\n";
    }

    return 0;
}

int ff(int x,int p,int fx,int fp){
    if(v[x].size()==1 and p!=0){
        if((c[x]^(fx^fp))==0)return 0;
        else return 1000000;
    }

    if(li[x][fx][fp])return dp[x][fx][fp];
    li[x][fx][fp]=true;

    dp[x][fx][fp]=ff2(x,p,(c[x]^(fx^fp)),fx,v[x].size()-1);
    return dp[x][fx][fp];
}

int ff2(int x,int p,int ost,int fp,int id){
    if(id==-1 and ost==0)return 0;
    else if(id==-1)return 1000000;

    if(us[x][ost][fp][id])return sp[x][ost][fp][id];
    us[x][ost][fp][id]=true;

    if(v[x][id]==p)sp[x][ost][fp][id]=ff2(x,p,ost,fp,id-1);
    else sp[x][ost][fp][id]=min( ff2(x,p,ost,fp,id-1)+ff(v[x][id],x,0,fp) , ff2(x,p,(ost^1),fp,id-1)+ff(v[x][id],x,1,fp)+1 );

    return sp[x][ost][fp][id];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 16 ms 27732 KB Output is correct
3 Correct 17 ms 27732 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 13 ms 27624 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 16 ms 27732 KB Output is correct
3 Correct 17 ms 27732 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 13 ms 27624 KB Output is correct
6 Correct 15 ms 27684 KB Output is correct
7 Correct 17 ms 27732 KB Output is correct
8 Correct 14 ms 27748 KB Output is correct
9 Correct 15 ms 27732 KB Output is correct
10 Correct 14 ms 27708 KB Output is correct
11 Correct 14 ms 27748 KB Output is correct
12 Correct 13 ms 27732 KB Output is correct
13 Correct 15 ms 27732 KB Output is correct
14 Correct 13 ms 27732 KB Output is correct
15 Correct 16 ms 27740 KB Output is correct
16 Correct 13 ms 27732 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 75180 KB Output is correct
2 Correct 265 ms 74568 KB Output is correct
3 Correct 258 ms 75508 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 75204 KB Output is correct
2 Correct 255 ms 74688 KB Output is correct
3 Correct 252 ms 75452 KB Output is correct
4 Correct 256 ms 54992 KB Output is correct
5 Correct 321 ms 57548 KB Output is correct
6 Correct 277 ms 58240 KB Output is correct
7 Correct 18 ms 27860 KB Output is correct
8 Correct 122 ms 37956 KB Output is correct
9 Correct 312 ms 57904 KB Output is correct
10 Correct 329 ms 58464 KB Output is correct
11 Correct 284 ms 59204 KB Output is correct
12 Correct 303 ms 60340 KB Output is correct
13 Correct 290 ms 56360 KB Output is correct
14 Correct 300 ms 58232 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 16 ms 27732 KB Output is correct
3 Correct 17 ms 27732 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 13 ms 27624 KB Output is correct
6 Correct 15 ms 27684 KB Output is correct
7 Correct 17 ms 27732 KB Output is correct
8 Correct 14 ms 27748 KB Output is correct
9 Correct 15 ms 27732 KB Output is correct
10 Correct 14 ms 27708 KB Output is correct
11 Correct 14 ms 27748 KB Output is correct
12 Correct 13 ms 27732 KB Output is correct
13 Correct 15 ms 27732 KB Output is correct
14 Correct 13 ms 27732 KB Output is correct
15 Correct 16 ms 27740 KB Output is correct
16 Correct 13 ms 27732 KB Output is correct
17 Correct 347 ms 75180 KB Output is correct
18 Correct 265 ms 74568 KB Output is correct
19 Correct 258 ms 75508 KB Output is correct
20 Correct 248 ms 75204 KB Output is correct
21 Correct 255 ms 74688 KB Output is correct
22 Correct 252 ms 75452 KB Output is correct
23 Correct 256 ms 54992 KB Output is correct
24 Correct 321 ms 57548 KB Output is correct
25 Correct 277 ms 58240 KB Output is correct
26 Correct 18 ms 27860 KB Output is correct
27 Correct 122 ms 37956 KB Output is correct
28 Correct 312 ms 57904 KB Output is correct
29 Correct 329 ms 58464 KB Output is correct
30 Correct 284 ms 59204 KB Output is correct
31 Correct 303 ms 60340 KB Output is correct
32 Correct 290 ms 56360 KB Output is correct
33 Correct 300 ms 58232 KB Output is correct
34 Correct 14 ms 27644 KB Output is correct
35 Correct 13 ms 27668 KB Output is correct
36 Correct 14 ms 27732 KB Output is correct
37 Correct 19 ms 27644 KB Output is correct
38 Correct 18 ms 27732 KB Output is correct
39 Correct 13 ms 27728 KB Output is correct
40 Correct 19 ms 27748 KB Output is correct
41 Correct 18 ms 27656 KB Output is correct
42 Correct 14 ms 27732 KB Output is correct
43 Correct 13 ms 27732 KB Output is correct
44 Correct 13 ms 27732 KB Output is correct
45 Correct 247 ms 75216 KB Output is correct
46 Correct 248 ms 74564 KB Output is correct
47 Correct 255 ms 75452 KB Output is correct
48 Correct 249 ms 54988 KB Output is correct
49 Correct 284 ms 57560 KB Output is correct
50 Correct 278 ms 58276 KB Output is correct
51 Correct 17 ms 27888 KB Output is correct
52 Correct 98 ms 38024 KB Output is correct
53 Correct 278 ms 57940 KB Output is correct
54 Correct 277 ms 58420 KB Output is correct
55 Correct 286 ms 59156 KB Output is correct
56 Correct 290 ms 60204 KB Output is correct
57 Correct 250 ms 56336 KB Output is correct
58 Correct 277 ms 58112 KB Output is correct
59 Correct 81 ms 37836 KB Output is correct
60 Correct 244 ms 55252 KB Output is correct
61 Correct 282 ms 57888 KB Output is correct
62 Correct 322 ms 58576 KB Output is correct
63 Correct 280 ms 58764 KB Output is correct
64 Correct 278 ms 58540 KB Output is correct
65 Correct 191 ms 60848 KB Output is correct
66 Correct 226 ms 60944 KB Output is correct
67 Correct 190 ms 67732 KB Output is correct
68 Correct 183 ms 67632 KB Output is correct
69 Correct 188 ms 67724 KB Output is correct
70 Correct 172 ms 67784 KB Output is correct