oj.uz

Submission #306745

# Submission time Handle Problem Language Result Execution time Memory
306745 2020-09-26T08:30:13 Z MrDomino Power Plant (JOI20_power) C++14
0 / 100
 4 ms 5120 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
int n;
int v[N];
int k[N];
int sub[N];
int sol;
vector<int> g[N];
string s;
int tot;

void dfs(int a, int p)
{
    sub[a] = v[a];
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dfs(b, a);
            sub[a] += sub[b];
            k[a] += k[b];
        }
    }
    if (sub[a] < tot && v[a] == 0)
    {
        sol = max(sol, k[a] + 1);
    }
    sol = max(sol, k[a]);
    k[a] -= v[a];
    k[a] = max(k[a], 0);
    if (v[a])
    {
        k[a] = max(k[a], 1);
    }
    sol = max(sol, k[a]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> s;
    for (int i = 1; i <= n; i++)
    {
        if (s[i - 1] == '1')
        {
            v[i] = 1;
            tot++;
        }
    }
    dfs(1, -1);
    cout << sol << "\n";
}

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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