oj.uz

답안 #306753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306753 2020-09-26T08:41:25 Z MrDomino Power Plant (JOI20_power) C++14
0 / 100
 4 ms 4992 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
int n;
vector<int> g[N];
int v[N];
int dp[N];
int sol;

void dfs(int a, int p)
{
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dfs(b, a);
        }
    }
    dp[a] = -v[a];
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dp[a] += dp[b];
        }
    }
    dp[a] = max(dp[a], v[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);
    }
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++)
    {
        if (s[i - 1] == '1')
        {
            v[i] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (v[i])
        {
            dfs(i, -1);
            sol = max(sol, dp[i]);
        }
    }
    cout << sol << "\n";
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -