oj.uz

Submission #972603

# Submission time Handle Problem Language Result Execution time Memory
972603 2024-04-30T18:14:06 Z kl0989e The Xana coup (BOI21_xanadu) C++17
5 / 100
 43 ms 22360 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;
vector<vi> graph(maxn);
vector<vi> dp(maxn,vi(4,1e9));// (on,on), (off,off), (off,on), (on,off)
vi onoff(maxn,0);

void dfs(int cur, int prev=-1) {
    if (graph[cur].size()==1 && cur!=0) {
        if (onoff[cur]) {
            dp[cur][0]=0;
            dp[cur][2]=0;
        }
        else {
            dp[cur][1]=0;
            dp[cur][3]=0;
        }
        return;
    }
    int sum1=0,sum2=0;
    int sig1=1,sig2=1;//1=on & 0=off
    int minc1=1e9,minc2=1e9;
    if (!onoff[cur]) {
        sig1=0;
        sig2=0;
    }
    for (auto to:graph[cur]) {
        if (to==prev) {
            continue;
        }
        dfs(to,cur);
        if (dp[to][0]+1<dp[to][1]) {
            sig1=1-sig1;
            sum1+=dp[to][0]+1;
            minc1=min(minc1,dp[to][1]-dp[to][0]-1);
        }
        else {
            sum1+=dp[to][1];
            minc1=min(minc1,dp[to][0]+1-dp[to][1]);
        }
        if (dp[to][3]+1<dp[to][2]) {
            sig2=1-sig2;
            sum2+=dp[to][3]+1;
            minc2=min(minc2,dp[to][2]-dp[to][3]-1);
        }
        else {
            sum2+=dp[to][2];
            minc2=min(minc1,dp[to][3]+1-dp[to][2]);
        }
        sum1=min(int(1e9),sum1);
        sum2=min(int(1e9),sum2);
    }
    //cout << "cur: " << cur << '\n' << sig1 << ' ' << sum1 << ' ' << minc1 << '\n' << sig2 << ' ' << sum2 << ' ' << minc2 << '\n';
    if (sig1) {
        dp[cur][2]=min(sum1,dp[cur][2]);
        dp[cur][1]=min(sum1+minc1,dp[cur][1]);
    }
    else {
        dp[cur][1]=min(sum1,dp[cur][1]);
        dp[cur][2]=min(sum1+minc1,dp[cur][2]);
    }
    if (sig2) {
        dp[cur][0]=min(sum2,dp[cur][0]);
        dp[cur][3]=min(sum2+minc2,dp[cur][3]);
    }
    else {
        dp[cur][3]=min(sum2,dp[cur][3]);
        dp[cur][0]=min(sum2+minc2,dp[cur][0]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a,b;
    for (int i=0; i<n-1; i++) {
        cin >> a >> b;
        graph[--a].pb(--b);
        graph[b].pb(a);
    }
    for (int i=0; i<n; i++) {
        cin >> onoff[i];
    }
    dfs(0);
    int ans=min(dp[0][0]+1,dp[0][1]);
    if (ans>=1e9) {
        cout << "impossible\n";
    }
    else {
        cout << ans << '\n';
    }
    /*for (int i=0; i<n; i++) {
        cout << "i: " << i+1 << " - ";
        for (int j=0; j<4; j++) {
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }*/
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8540 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 6 ms 8540 KB Output is correct
6 Correct 6 ms 8536 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 6 ms 8540 KB Output is correct
9 Correct 6 ms 8540 KB Output is correct
10 Correct 7 ms 8536 KB Output is correct
11 Correct 6 ms 8540 KB Output is correct
12 Incorrect 6 ms 8540 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 22352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 22360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8540 KB Output is correct
2 Correct 6 ms 8540 KB Output is correct
3 Correct 6 ms 8540 KB Output is correct
4 Correct 6 ms 8540 KB Output is correct
5 Correct 6 ms 8540 KB Output is correct
6 Correct 6 ms 8536 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 6 ms 8540 KB Output is correct
9 Correct 6 ms 8540 KB Output is correct
10 Correct 7 ms 8536 KB Output is correct
11 Correct 6 ms 8540 KB Output is correct
12 Incorrect 6 ms 8540 KB Output isn't correct
13 Halted 0 ms 0 KB -