Submission #627043

#	Time	Username	Problem	Language	Result	Execution time	Memory
627043		tamthegod	Road Closures (APIO21_roads)	C++14	5 / 100	500 ms	85544 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
ll f[2001][2001];
int tmp[maxN];
int k;
vector<pair<int, int>> adj[maxN];
void dfs(int u, int par)
{
    for(auto a : adj[u])
    {
        int v = a.fi, w = a.se;
        if(v == par) continue;
        dfs(v, u);
        for(int i=0; i<=k; i++) tmp[i] = f[u][i];
        tmp[k] += f[v][0] + w;
        for(int i=k-1; i>=0; i--)
            tmp[i] = min(f[u][i] + f[v][0] + w, f[u][i + 1] + f[v][1]);
        for(int i=k-1; i>=1; i--)
            tmp[i] = min(tmp[i], tmp[i + 1]);
        for(int i=0; i<=k; i++) f[u][i] = tmp[i];
        if(u == 1 && v == 3)
        {
           // cout << f[1][1];exit(0);
        }
    }
}
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
    vector<ll> res;
    bool ok = true;
    ll sum = 0;
    for(int i=0; i<n-1; i++)
    {
        int u = U[i] + 1, v = V[i] + 1, w = W[i];
        //cout << u << " " << v << '\n';
        sum += w;
        if(U[i] != i || V[i] != i + 1) ok = false;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    if(adj[1].size() == n - 1)
    {
        vector<int> vc;
        for(int i=0; i<n-1; i++) vc.pb(W[i]);
        sort(vc.begin(), vc.end());
        for(int i=0; i<n; i++)
        {
            res.pb(sum);
            sum -= vc.back();
            vc.pop_back();
        }
        return res;
    }
    if(ok)
    {
       res.pb(sum);
       f[1][1] = W[0];
       for(int i=2; i<n; i++)
       {
           f[i][0] = f[i - 1][1];
           f[i][1] = min(f[i - 1][0], f[i - 1][1]) + W[i - 1];
       }
       res.pb(min(f[n - 1][0], f[n - 1][1]));
       while(res.size() != n) res.pb(0);
       return res;
    }
    for(int _k=n-1; _k>=1; _k--)
    {
        k = _k;
        memset(f, 0, sizeof f);
        dfs(1, 0);
      //  cout << f[1][0];exit(0);
        res.pb(f[1][0]);
    }
    res.pb(sum);
    reverse(res.begin(), res.end());
    return res;
}
/*void Solve()
{
    int n;
    cin >> n;
    vector<int> u(n), v(n), w(n);
    for(int i=0; i<n-1; i++) cin >> u[i];
    for(int i=0; i<n-1; i++) cin >> v[i];
    for(int i=0; i<n-1; i++) cin >> w[i];
    vector<ll> res = minimum_closure_costs(n, u, v, w);
    for(int v : res) cout << v << " ";
}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}*/

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:52:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     if(adj[1].size() == n - 1)
      |        ~~~~~~~~~~~~~~^~~~~~~~
roads.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |        while(res.size() != n) res.pb(0);
      |              ~~~~~~~~~~~^~~~

• Subtask 1: 5 / 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