oj.uz

Submission #955629

# Submission time Handle Problem Language Result Execution time Memory
955629 2024-03-31T07:17:27 Z Neco_arc Power Plant (JOI20_power) C++17
6 / 100
 1500 ms 6744 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Power Plant"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n;
int cl[maxn];
vector<int> edges[maxn];

namespace Sub1
{
    int a[maxn];

    int calc(int u, int par) {
        int ans = 0;
        for(int v : edges[u]) if(v != par) ans += calc(v, u) > 0;
        if(a[u]) ans = max(ans, 1);
        return ans;
    }

    int solve()
    {
        int ans = 0;
        fi(x, 1, (1 << n) - 1)
        {
            fi(i, 1, n) {
                a[i] = 0;
                if(getbit(x, i - 1)) a[i] = cl[i];
            }

            int sum = 0;
            fi(i, 1, n) if(cl[i])
            {
                int w = calc(i, 0);
                if(w > 1) sum --;
                else sum += (w == 1) && a[i];
            }
            ans = max(ans, sum);
//
//            if(x == 29310) {
////                 fi(i, 1, n) cout << calc(i, 0) << '\n';
////                fi(i, 1, n) cout << a[i];
////                exit(0);
//            }

        }
        return ans;
    }

}

namespace Sub2
{
    int res = 1;
    int dp[maxn];

    void dfs(int u, int par)
    {
        vector<int> P;
        for(int v : edges[u]) if(v != par) {
            dfs(v, u);
            P.push_back(dp[v]);
        }

        sort(all(P), greater<int>());

        int ans = cl[u];
        int sum = 0;

        if(P.size() >= 1)
        {
            res = max(res, P[0] + cl[u]), ans = max(ans, P[0] + cl[u]);

            fi(i, 0, P.size() - 1) {
                sum += P[i];
                if(i > 1) res = max(res, sum - cl[u]), ans = max(ans, sum - cl[u]);
            }
            dp[u] = sum;
        }

        if(cl[u]) dp[u] = max(dp[u] - 1, 1);
    }

    int solve()
    {
        dfs(1, 0);
        return res;
    }

}


void Input()
{
    cin >> n;

    fi(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y), edges[y].push_back(x);
    }

    fi(i, 1, n) {
        char x; cin >> x;
        cl[i] = x - '0';
    }
}

pair<int, int> E[maxn];
void gen()
{
    n = GetRandom(2, 15);
    fi(i, 1, n - 1) {
        int x = i + 1, y = GetRandom(1, i);
        edges[x].push_back(y), edges[y].push_back(x);
        E[i] = {x, y};
    }

    fi(i, 1, n) cl[i] = GetRandom(0, 1);
}

void Print()
{
    cout << n << '\n';
    fi(i, 1, n - 1) {
        cout << E[i].first << " " << E[i].second << '\n';
    }
    fi(i, 1, n) cout << cl[i];
    cout << '\n';
    cout << "-----------------------\n";
}


void solve()
{

    Input();
//    gen();

    cout << Sub1::solve();


}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

power.cpp: In function 'int Sub1::solve()':
power.cpp:50:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   50 |                 if(getbit(x, i - 1)) a[i] = cl[i];
      |                              ~~^~~
power.cpp:8:28: note: in definition of macro 'getbit'
    8 | #define getbit(x,i) ((x >> i)&1)
      |                            ^
power.cpp: In function 'void Sub2::dfs(int, int)':
power.cpp:12:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define fi(i, a, b) for(int i = a; i <= b; i++)
......
   96 |             fi(i, 0, P.size() - 1) {
      |                ~~~~~~~~~~~~~~~~~~     
power.cpp:96:13: note: in expansion of macro 'fi'
   96 |             fi(i, 0, P.size() - 1) {
      |             ^~
power.cpp: In function 'int main()':
power.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 12 ms 6624 KB Output is correct
3 Correct 24 ms 6620 KB Output is correct
4 Correct 42 ms 6492 KB Output is correct
5 Correct 68 ms 6744 KB Output is correct
6 Correct 64 ms 6604 KB Output is correct
7 Correct 105 ms 6488 KB Output is correct
8 Correct 122 ms 6600 KB Output is correct
9 Correct 51 ms 6492 KB Output is correct
10 Correct 68 ms 6488 KB Output is correct
11 Correct 112 ms 6488 KB Output is correct
12 Correct 77 ms 6488 KB Output is correct
13 Correct 68 ms 6492 KB Output is correct
14 Correct 92 ms 6488 KB Output is correct
15 Correct 26 ms 6616 KB Output is correct
16 Correct 34 ms 6488 KB Output is correct
17 Correct 112 ms 6492 KB Output is correct
18 Correct 104 ms 6492 KB Output is correct
19 Correct 18 ms 6492 KB Output is correct
20 Correct 50 ms 6744 KB Output is correct
21 Correct 101 ms 6600 KB Output is correct

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 12 ms 6624 KB Output is correct
3 Correct 24 ms 6620 KB Output is correct
4 Correct 42 ms 6492 KB Output is correct
5 Correct 68 ms 6744 KB Output is correct
6 Correct 64 ms 6604 KB Output is correct
7 Correct 105 ms 6488 KB Output is correct
8 Correct 122 ms 6600 KB Output is correct
9 Correct 51 ms 6492 KB Output is correct
10 Correct 68 ms 6488 KB Output is correct
11 Correct 112 ms 6488 KB Output is correct
12 Correct 77 ms 6488 KB Output is correct
13 Correct 68 ms 6492 KB Output is correct
14 Correct 92 ms 6488 KB Output is correct
15 Correct 26 ms 6616 KB Output is correct
16 Correct 34 ms 6488 KB Output is correct
17 Correct 112 ms 6492 KB Output is correct
18 Correct 104 ms 6492 KB Output is correct
19 Correct 18 ms 6492 KB Output is correct
20 Correct 50 ms 6744 KB Output is correct
21 Correct 101 ms 6600 KB Output is correct
22 Execution timed out 1558 ms 6492 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 12 ms 6624 KB Output is correct
3 Correct 24 ms 6620 KB Output is correct
4 Correct 42 ms 6492 KB Output is correct
5 Correct 68 ms 6744 KB Output is correct
6 Correct 64 ms 6604 KB Output is correct
7 Correct 105 ms 6488 KB Output is correct
8 Correct 122 ms 6600 KB Output is correct
9 Correct 51 ms 6492 KB Output is correct
10 Correct 68 ms 6488 KB Output is correct
11 Correct 112 ms 6488 KB Output is correct
12 Correct 77 ms 6488 KB Output is correct
13 Correct 68 ms 6492 KB Output is correct
14 Correct 92 ms 6488 KB Output is correct
15 Correct 26 ms 6616 KB Output is correct
16 Correct 34 ms 6488 KB Output is correct
17 Correct 112 ms 6492 KB Output is correct
18 Correct 104 ms 6492 KB Output is correct
19 Correct 18 ms 6492 KB Output is correct
20 Correct 50 ms 6744 KB Output is correct
21 Correct 101 ms 6600 KB Output is correct
22 Execution timed out 1558 ms 6492 KB Time limit exceeded
23 Halted 0 ms 0 KB -