oj.uz

Submission #293160

# Submission time Handle Problem Language Result Execution time Memory
293160 2020-09-07T17:13:11 Z CaroLinda Power Plant (JOI20_power) C++14
0 / 100
 4 ms 4992 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mk make_pair
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define sz(x) (int)(x.size())

const int MAXN = 2e5+10 ;

using namespace std ;

int N ;
int dp[MAXN][2] ;
vector<int> adj[MAXN] ;
bool isPower[MAXN] ;
char str[MAXN] ;

void dfs(int x, int dad)
{

    int mx[2] = {0,0} ;
    int soma1 = 0 ;

    for(auto e : adj[x] )
    {
        if(e == dad) continue ;

        dfs(e,x) ;

        lp(i,0,2) mx[i] = max(mx[i] , dp[e][i]) ;
        soma1 += dp[e][1] ;
    }

    if(!isPower[x])
    {
        dp[x][0] = max( soma1, mx[0] ) ;
        dp[x][1] = soma1 ;
    }
    else
    {
        dp[x][0] = max( mx[1] + 1 , soma1 - 1 ) ;
        dp[x][1] = max( 1 , soma1 - 1 ) ;
    }

}

int main()
{
    scanf("%d", &N) ;
    for(int i = 1 , u ,v ; i < N ; i++ )
    {
        scanf("%d%d", &u, &v ) ;

        adj[u].pb(v) ;
        adj[v].pb(u) ;
    }

    scanf("%s", str ) ;
    lp(i,0,N) isPower[i+1] = ( str[i] == '1' ) ;

    dfs(1,-1) ;
    printf("%d\n" , dp[1][0]) ;
}

Compilation message

power.cpp: In function 'int main()':
power.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     scanf("%d", &N) ;
      |     ~~~~~^~~~~~~~~~
power.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d%d", &u, &v ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%s", str ) ;
      |     ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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