Submission #627440

#	Time	Username	Problem	Language	Result	Execution time	Memory
627440		Tien_Noob	Road Closures (APIO21_roads)	C++17	0 / 100	191 ms	2516 KiB

roads

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include <roads.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 2e3;
long long dp[N + 1][2];
vector<pair<int, int> > adj[N + 1];
void DFS(int u, int p, int k)
{
    dp[u][0] = dp[u][1] = 0;
    vector<long long> f;
    long long sum = 0;
    for (auto &[v, w] : adj[u])
    {
        if (v == p)
        {
            continue;
        }
        DFS(v, u, k);
        f.push_back(dp[v][1] + w - dp[v][0]);
        sum += dp[v][0];
    }
    sort(f.begin(), f.end(), greater<long long> () );
    for (int t = 0; t < 2; ++ t)
    {
        while(f.size() > max(0, k - t))
        {
            sum += f.back();
            f.pop_back();
        }
        dp[u][t] = sum;
    }
    dp[u][0] = min(dp[u][0], dp[u][1]);
}
vector<long long>  minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
    if (n > N)
    {
        exit(0);
    }
    for (int i = 0; i < n - 1; ++ i)
    {
        int u = U[i] + 1, v = V[i] + 1;
        adj[u].emplace_back(v, W[i]);
        adj[v].emplace_back(u, W[i]);
    }
    vector<long long> res;
    for (int k = 0; k < n; ++ k)
    {
        DFS(1, 0, k);
        res.push_back(dp[1][0]);
    }
    return res;
}
/*void read()
{
    vector<long long> t = minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});
    for (long long x : t)
    {
        cerr << x << ' ';
    }
}
void solve()
{

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}*/

Compilation message (stderr)

roads.cpp: In function 'void DFS(int, int, int)':
roads.cpp:29:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   29 |         while(f.size() > max(0, k - t))
      |               ~~~~~~~~~^~~~~~~~~~~~~~~

• 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