oj.uz

답안 #867079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867079 2023-10-27T16:36:47 Z HossamHero7 The Xana coup (BOI21_xanadu) C++14
55 / 100
 71 ms 25024 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
vector<vector<int>> adj;
vector<int> on;
const int N = 1e5+5;
ll dp[N][3][2];
ll solve(int node,int par,int pressed,bool color){
    ll &ret = dp[node][pressed][color];
    if(~ret) return ret;
    ret = 1e9;
    if(pressed != 1){
        int sz = adj[node].size();
        if(node) sz --;
        for(int mask=0;mask<(1<<sz);mask++){
            bool changed = __builtin_popcount(mask) & 1;
            if((color^changed)) continue;
            ll c = 0;
            int idx = 0;
            for(auto ch : adj[node]){
                if(ch == par) continue;
                if(((mask>>idx)&1)) c += solve(ch,node,1,on[ch]^1) + 1;
                else c += solve(ch,node,0,on[ch]);
                idx ++;
            }
            ret = min(ret,c);
        }
    }
    if(pressed != 0){
        int sz = adj[node].size();
        if(node) sz --;
        for(int mask=0;mask<(1<<sz);mask++){
            bool changed = __builtin_popcount(mask) & 1;
            if(pressed == 1 && (color^changed)) continue;
            if(pressed == 2 && !((color^changed))) continue;
            ll c = 0;
            int idx = 0;
            for(auto ch : adj[node]){
                if(ch == par) continue;
                if(((mask>>idx)&1)) c += solve(ch,node,1,on[ch]) + 1;
                else c += solve(ch,node,0,on[ch]^1);
                idx ++;
            }
            if(pressed == 2) c ++;
            ret = min(ret,c);
        }
    }
    return ret;
}
void solve(){
    int n;
    cin>>n;
    adj.resize(n);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a -- , b --;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    on.resize(n);
    for(int i=0;i<n;i++){
        int x;cin>>x;
        if(x) on[i] = 1;
    }
    memset(dp,-1,sizeof(dp));
    ll ans = solve(0,n,2,on[0]);
    if(ans >= 1e9) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Incorrect 1 ms 4956 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 24924 KB Output is correct
2 Correct 48 ms 24756 KB Output is correct
3 Correct 62 ms 25024 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 24756 KB Output is correct
2 Correct 58 ms 24912 KB Output is correct
3 Correct 54 ms 24916 KB Output is correct
4 Correct 62 ms 10324 KB Output is correct
5 Correct 71 ms 10836 KB Output is correct
6 Correct 46 ms 11020 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 18 ms 7644 KB Output is correct
9 Correct 45 ms 12080 KB Output is correct
10 Correct 51 ms 12120 KB Output is correct
11 Correct 47 ms 12880 KB Output is correct
12 Correct 47 ms 13136 KB Output is correct
13 Correct 41 ms 11344 KB Output is correct
14 Correct 50 ms 11856 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Incorrect 1 ms 4956 KB Output isn't correct
16 Halted 0 ms 0 KB -