Submission #708328

#	Time	Username	Problem	Language	Result	Execution time	Memory
708328		600Mihnea	Road Closures (APIO21_roads)	C++17	0 / 100	2076 ms	21188 KiB

roads

#include "roads.h"

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define ve vector
#define vei vector<int> 
#define vell vector<ll> 
#define sz(x) ((int)x.size())
#define each(it, x) for (auto &it : x)
#define debug(x) cout << #x << " = " << x << "\n";
#define FU function
#define VO void

vell minimum_closure_costs(int N, vei U, vei V, vei W) {
    int n = N;
    assert(sz(U) == n - 1);
    assert(sz(V) == n - 1);
    assert(sz(W) == n - 1);
#ifdef ONPC
    debug(n);
    each(it, U) cout << it << " "; cout << "\n";
    each(it, V) cout << it << " "; cout << "\n";
    each(it, W) cout << it << " "; cout << "\n";
#endif
    ve<ve<pii>> g(n);
    for (int i = 0; i < n - 1; i++)
        g[U[i]].pb({ V[i], W[i] }),
        g[V[i]].pb({ U[i], W[i] });
    vei ord, deg(n, 0), pap(n, -1);
    vell edgeup(n, 0);
    for (int i = 0; i < n; i++) deg[i] = sz(g[i]);
    FU<VO(int, int)>build = [&](int a, int par)
    {
        pap[a] = par;
        ve<pii> kids;
        ord.pb(a);
        each(it, g[a])
        {
            int b = it.f, c = it.s;
            if (b == par) continue;
            edgeup[b] = c;
            build(b, a);
            kids.pb({ b, c });
        }
        g[a] = kids;
    };
    build(0, -1);
    reverse(all(ord));

    vell sol(n, 0);

    for (int k = 0; k < n; k++)
    {
        vell dp0(n, 0), dp1(n, 0);
        // 0 => are gradul <= k + 0
        // 1 => are gradul <= k + 1
        ll print = 0;
        each(a, ord)
        {
            if (deg[a] < k)
            {
                dp0[a] = dp1[a] = 0;
                continue;
            }
            each(rem, vei({ k - 1, k }))
            {
                // sterg muchia => dp1 + cost
                // pastrez muchia => dp0

                int total = sz(g[a]);
                int pastrez = min(total, rem);

                ll su = 0;
                each(it, g[a]) su += dp1[it.first] + it.second;
                if (a > 0 && deg[pap[a]] < k) su += edgeup[a];
                vector<ll> difs;
                each(it, g[a]) difs.pb(min(0LL, dp0[it.first] - dp1[it.first] - it.second));
                if (a > 0 && deg[pap[a]] < k) difs.push_back(-edgeup[a]);
                sort(difs.begin(), difs.end());

                for (int i = 0; i < pastrez; i++)
                {
                    assert(0 <= i && i < sz(difs));
                    su += difs[i];
                }

                if (rem == k - 1) dp0[a] = su; else dp1[a] = su;
            }
            if (a == 0)
            {
                print += dp1[a];
            }
            else
            {
                if (deg[pap[a]] < k)
                {
                    print += dp0[a];
                }
            }
            assert(dp0[a] >= dp1[a]);
        }
        sol[k] = print;
    }

    return sol;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22