Submission #298768

#	Time	Username	Problem	Language	Result	Execution time	Memory
298768		Pro_ktmr	Power Plant (JOI20_power)	C++14	100 / 100	293 ms	29432 KiB

power

#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int N;
int A[200000], B[200000];
vector<pair<int,int>> E[200000];
bool gen[200000];

bool SUM[200000] = {};
int sum[200000];

int dp[400000];
int solve(int n, int p, int e){
    if(dp[e] != -1) return dp[e];
    if(gen[n]){
        dp[e] = 1;
        int tmp = -1;
        if(SUM[n]) tmp += sum[n] - solve(p, n, e%N + N*((e/N)^1));
        else{
            rep(i, E[n].size()){
                if(E[n][i].first == p) continue;
                tmp += solve(E[n][i].first, n, E[n][i].second);
            }
        }
        dp[e] = max(dp[e], tmp);
    }
    else{
        dp[e] = 0;
        int tmp = 0;
        if(SUM[n]) tmp += sum[n] - solve(p, n, e%N + N*((e/N)^1));
        else{
            rep(i, E[n].size()){
                if(E[n][i].first == p) continue;
                tmp += solve(E[n][i].first, n, E[n][i].second);
            }
        }
        dp[e] = max(dp[e], tmp);
    }
    return dp[e];
}

void dfs(int n, int p){
    sum[n] = 0;
    rep(i, E[n].size()){
        sum[n] += solve(E[n][i].first, n, E[n][i].second);
    }
    SUM[n] = true;
    rep(i, E[n].size()){
        if(E[n][i].first == p) continue;
        dfs(E[n][i].first, n);
    }
}

signed main(){
    scanf("%d", &N);
    rep(i, N-1){
        scanf("%d%d", &A[i], &B[i]);
        A[i]--; B[i]--;
        E[A[i]].pb({B[i],i});
        E[B[i]].pb({A[i],N+i});
    }
    rep(i, N){
        char C;
        scanf(" %c", &C);
        gen[i] = C-'0';
    }

    memset(dp, -1, sizeof(dp));
    rep(i, E[0].size()) solve(E[0][i].first, 0, E[0][i].second);
    dfs(0, -1);

    int ans = 0;
    rep(i, N){
        if(!gen[i]) continue;
        int tmp = 0;
        rep(j, E[i].size()){
            tmp = max(tmp, solve(E[i][j].first, i, E[i][j].second));
        }
        ans = max(ans, tmp+1);
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

power.cpp: In function 'int solve(int, int, int)':
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:34:13: note: in expansion of macro 'rep'
   34 |             rep(i, E[n].size()){
      |             ^~~
power.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
power.cpp:34:13: note: in expansion of macro 'rep'
   34 |             rep(i, E[n].size()){
      |             ^~~
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:46:13: note: in expansion of macro 'rep'
   46 |             rep(i, E[n].size()){
      |             ^~~
power.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
power.cpp:46:13: note: in expansion of macro 'rep'
   46 |             rep(i, E[n].size()){
      |             ^~~
power.cpp: In function 'void dfs(int, int)':
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:58:5: note: in expansion of macro 'rep'
   58 |     rep(i, E[n].size()){
      |     ^~~
power.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
power.cpp:58:5: note: in expansion of macro 'rep'
   58 |     rep(i, E[n].size()){
      |     ^~~
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:62:5: note: in expansion of macro 'rep'
   62 |     rep(i, E[n].size()){
      |     ^~~
power.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
power.cpp:62:5: note: in expansion of macro 'rep'
   62 |     rep(i, E[n].size()){
      |     ^~~
power.cpp: In function 'int main()':
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:70:5: note: in expansion of macro 'rep'
   70 |     rep(i, N-1){
      |     ^~~
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:76:5: note: in expansion of macro 'rep'
   76 |     rep(i, N){
      |     ^~~
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:83:5: note: in expansion of macro 'rep'
   83 |     rep(i, E[0].size()) solve(E[0][i].first, 0, E[0][i].second);
      |     ^~~
power.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
power.cpp:83:5: note: in expansion of macro 'rep'
   83 |     rep(i, E[0].size()) solve(E[0][i].first, 0, E[0][i].second);
      |     ^~~
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:87:5: note: in expansion of macro 'rep'
   87 |     rep(i, N){
      |     ^~~
power.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
power.cpp:90:9: note: in expansion of macro 'rep'
   90 |         rep(j, E[i].size()){
      |         ^~~
power.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
power.cpp:90:9: note: in expansion of macro 'rep'
   90 |         rep(j, E[i].size()){
      |         ^~~
power.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
power.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%d%d", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
power.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf(" %c", &C);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53