Submission #627017

#	Time	Username	Problem	Language	Result	Execution time	Memory
627017		tamthegod	Road Closures (APIO21_roads)	C++14	12 / 100	99 ms	34160 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 = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
ll f[maxN][2];
vector<pair<int, int>> adj[maxN];
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;
    }
}
/*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:30: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]
   30 |     if(adj[1].size() == n - 1)
      |        ~~~~~~~~~~~~~~^~~~~~~~
roads.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |        while(res.size() != n) res.pb(0);
      |              ~~~~~~~~~~~^~~~
roads.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

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