oj.uz

Submission #320488

# Submission time Handle Problem Language Result Execution time Memory
320488 2020-11-08T20:57:45 Z Lawliet Power Plant (JOI20_power) C++17
0 / 100
 4 ms 5100 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200010;

int n;
int ans;

int sum[MAXN];

string s;

vector<int> adj[MAXN];

int getDP(int node)
{
    if( s[node - 1] == '0' ) return sum[node];
    return max( 1 , sum[node] - 1 );
}

void DFSCalculate(int cur, int p)
{
    for(int i = 0 ; i < (int)adj[cur].size() ; i++)
    {
        int viz = adj[cur][i];

        if( viz == p ) continue;

        DFSCalculate( viz , cur );
        sum[cur] += getDP( viz );
    }
}

void DFSRerooting(int cur, int p)
{
    ans = max( ans , getDP(cur) );

    for(int i = 0 ; i < (int)adj[cur].size() ; i++)
    {
        int viz = adj[cur][i];

        if( viz == p ) continue;

        sum[cur] -= getDP(viz);
        sum[viz] += getDP(cur);

        DFSRerooting( viz , cur );

        sum[viz] -= getDP(cur);
        sum[cur] += getDP(viz);
    }
}

int main()
{
    cin >> n;

    for(int i = 1 ; i < n ; i++)
    {
        int U, V;
        scanf("%d %d",&U,&V);

        adj[U].push_back( V );
        adj[V].push_back( U );
    }

    cin >> s;

    DFSCalculate( 1 , 1 );
    DFSRerooting( 1 , 1 );

    printf("%d\n",ans);
}

Compilation message

power.cpp: In function 'int main()':
power.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%d %d",&U,&V);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 3 ms 4972 KB Output is correct
5 Correct 3 ms 4972 KB Output is correct
6 Correct 3 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Incorrect 4 ms 4972 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 4 ms 5100 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 3 ms 4972 KB Output is correct
5 Correct 3 ms 4972 KB Output is correct
6 Correct 3 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Incorrect 4 ms 4972 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 4 ms 5100 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 3 ms 4972 KB Output is correct
5 Correct 3 ms 4972 KB Output is correct
6 Correct 3 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Incorrect 4 ms 4972 KB Output isn't correct
9 Halted 0 ms 0 KB -