oj.uz

Submission #1024374

# Submission time Handle Problem Language Result Execution time Memory
1024374 2024-07-16T02:51:15 Z KienTran Power Plant (JOI20_power) C++14
0 / 100
 2 ms 6492 KB 
#include <bits/stdc++.h>

using namespace std;

const int O = 2e5 + 5;
const int N = (1 << 10) + 5;
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};

int n, f[2][2][O];
vector <int> g[O];
bool a[O];

void dfs(int u, int par = 0){
    int dif0 = 0, dif1 = 0;
    for (int v : g[u]){
        if (v != par){
            dfs(v, u);
            f[0][0][u] += f[0][0][v];
            f[1][1][u] += max({f[1][1][v], f[0][0][v], f[1][0][v]});
            f[0][1][u] += f[0][0][v];
            dif0 = max(dif0, f[0][1][v] - f[0][0][v]);
            dif1 = max(dif1, f[1][1][v] - f[0][0][v]);
        }
    }
    f[1][0][u] += a[u];
    f[1][1][u] -= a[u];
    f[0][1][u] = f[0][1][u] + max(max((int)a[u], dif0), a[u] + dif1);
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++ i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; ++ i){
        char x; cin >> x;
        a[i] = (x == '1');
    }

    dfs(1);

    int res = 0;
    for (int i = 0; i < 2; ++ i){
        for (int j = 0; j < 2; ++ j){
            //if (!(i == 1 && j == 0)){
                //for (int z = 1; z <= n; ++ z) cout << i << " " << j << " " << z << " = " << f[i][j][z] << endl;
            //}
            res = max(res, f[i][j][1]);
        }
    }

    cout << res;
}
/**
5
1 2
2 3
3 4
4 5
2
1 1
2 1
**/

Compilation message

power.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Incorrect 2 ms 6488 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Incorrect 2 ms 6488 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Incorrect 2 ms 6488 KB Output isn't correct
9 Halted 0 ms 0 KB -