5376 2023. 04. 27 06:18:16 anon Energiatakarékos ellenőrzés cpp17 Time limit exceeded 30/100 584ms 22416 KiB 
#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define pb push_back
#define xx first
#define yy second
#define mp make_pair

#define all(x) x.begin(), x.end()
#define sz(x) x.size()

typedef long long ll;

using namespace std;

const double PI = acos(-1);
const ll INF = 1LL << 62;

int main()
{
    FastIO;

    ll i, a, b, r, c, s1, s2, N;

    cin >> N;

    vector<vector<ll>> g(N + 1);

    for(i = 1; i < N; i++)
    {
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<ll> sol(N + 1, -1);
    vector<ll> tme(N + 1, 0);

    vector<ll> vis(N + 1, false);
    vis[1] = true;

    vector<ll> q;
    q.pb(1);

    while(q.size())
    {
        r = q.back();

        if(sz(g[r]) == 1 && r != 1)
        {
            sol[r] = 0;
            tme[r] = 1;

            q.pop_back();

            continue;
        }

        c = false;

        for(auto x : g[r])
        {
            if(vis[x])
                continue;

            c = true;
            vis[x] = true;

            q.push_back(x);

            break;
        }

        if(c)
            continue;

        sol[r] = 0;
        tme[r] = sz(g[r]);

        for(auto x : g[r])
        {
            if(sol[x] == -1)
                continue;

            sol[r] += min(1 + sol[x] + tme[x], 8 + sol[x]);
            tme[r] += tme[x];
        }

        q.pop_back();
    }

    cout << sol[1] << endl;

    return 0;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1700 KiB
2 Accepted 54ms 18532 KiB
subtask2 0/5
3 Time limit exceeded 555ms 10180 KiB
4 Time limit exceeded 564ms 10444 KiB
5 Time limit exceeded 584ms 10200 KiB
6 Time limit exceeded 532ms 10436 KiB
7 Time limit exceeded 541ms 10624 KiB
subtask3 15/15
8 Accepted 3ms 2880 KiB
9 Accepted 3ms 3124 KiB
10 Accepted 3ms 3008 KiB
11 Accepted 3ms 3012 KiB
12 Accepted 3ms 3292 KiB
13 Accepted 3ms 3152 KiB
14 Accepted 2ms 3260 KiB
subtask4 15/15
15 Accepted 3ms 3268 KiB
16 Accepted 3ms 3496 KiB
17 Accepted 3ms 3476 KiB
18 Accepted 3ms 3416 KiB
19 Accepted 3ms 3644 KiB
20 Accepted 3ms 3724 KiB
21 Accepted 3ms 3632 KiB
subtask5 0/65
22 Accepted 56ms 20300 KiB
23 Accepted 57ms 20428 KiB
24 Accepted 54ms 20512 KiB
25 Accepted 54ms 20660 KiB
26 Accepted 54ms 20512 KiB
27 Accepted 59ms 20688 KiB
28 Accepted 59ms 21500 KiB
29 Accepted 57ms 21100 KiB
30 Accepted 57ms 20928 KiB
31 Accepted 57ms 20652 KiB
32 Accepted 57ms 20428 KiB
33 Accepted 56ms 20392 KiB
34 Time limit exceeded 541ms 11800 KiB
35 Time limit exceeded 558ms 11928 KiB
36 Time limit exceeded 545ms 11828 KiB
37 Time limit exceeded 573ms 12360 KiB
38 Accepted 109ms 21876 KiB
39 Accepted 50ms 22120 KiB
40 Accepted 45ms 22416 KiB