Submission #886502

#	Time	Username	Problem	Language	Result	Execution time	Memory
886502		rukashii	Power Plant (JOI20_power)	C++17	0 / 100	14 ms	512 KiB

power

#include <bits/stdc++.h>
using namespace std;

#define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
#define int long long

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
void setIO(string s = "") {
    if (s.size()) setIn(s+".inp"), setOut(s+".out");
}

const int maxn = 2002;

string s;
vector <int> adj[maxn];
int n;

namespace Sub1
{
    const int s1maxn = 20;

    int on[maxn], sub[maxn];
    bool en[maxn];
    int ans, res;

    void dfs(int u, int par)
    {
        en[u] = on[u] && (s[u] == '1');
        ans += en[u];
        sub[u] = ((s[u] == '1'));

        for (int v : adj[u])
        {
            if (v == par)
                continue;
            
            Sub1::dfs(v, u);
            en[u] |= en[v];

            if ((on[u] && (s[u] == '1')) && en[v])
                ans -= (sub[v] - (on[v] && (s[v] == '1')));
            else
                sub[u] += sub[v];
        }
    }

    void solve()
    {
        for (int msk = 0; msk < (1 << n); msk++)
        {
            for (int i = 0; i < n; i++)
            {
                if (((msk >> i) & 1))
                    on[i + 1] = 1;
                else
                    on[i + 1] = 0;
            }

            // memset(en, 0, sizeof(en));
            ans = 0;
            Sub1::dfs(1, 1);

            // cout << msk << ' ' << ans << '\n';
            res = max(res, ans);
        }

        cout << res;
    }
} // namespace Sub1


signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    cin >> s;
    s = "." + s;

    if (n <= 16)
        return Sub1::solve(), 0;
}

Compilation message (stderr)

power.cpp: In function 'void setIn(std::string)':
power.cpp:7:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | void setIn(string s) { freopen(s.c_str(), "r", stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
power.cpp: In function 'void setOut(std::string)':
power.cpp:8:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | void setOut(string s) { freopen(s.c_str(), "w", stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
power.cpp: In function 'int main()':
power.cpp:4:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:76:5: note: in expansion of macro 'file'
   76 |     file;
      |     ^~~~
power.cpp:4:86: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:76:5: note: in expansion of macro 'file'
   76 |     file;
      |     ^~~~

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