oj.uz

Submission #626979

# Submission time Handle Problem Language Result Execution time Memory
626979 2022-08-12T03:58:34 Z tamthegod Road Closures (APIO21_roads) C++14
5 / 100
 77 ms 32232 KB 
#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 - 1) 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

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 - 1) res.pb(0);
      |              ~~~~~~~~~~~^~~~~~~~
roads.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 23872 KB Output is correct
3 Correct 13 ms 23960 KB Output is correct
4 Correct 14 ms 23912 KB Output is correct
5 Correct 14 ms 23724 KB Output is correct
6 Correct 13 ms 23776 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct
9 Correct 16 ms 23848 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23708 KB Output is correct
12 Correct 40 ms 28740 KB Output is correct
13 Correct 59 ms 32232 KB Output is correct
14 Correct 61 ms 31432 KB Output is correct
15 Correct 77 ms 32104 KB Output is correct
16 Correct 75 ms 32192 KB Output is correct
17 Correct 63 ms 32192 KB Output is correct
18 Correct 13 ms 23752 KB Output is correct
19 Correct 57 ms 31516 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23776 KB Output is correct
2 Incorrect 53 ms 30756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 13 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 13 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 32232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 32232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 23872 KB Output is correct
3 Correct 13 ms 23960 KB Output is correct
4 Correct 14 ms 23912 KB Output is correct
5 Correct 14 ms 23724 KB Output is correct
6 Correct 13 ms 23776 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 23892 KB Output is correct
9 Correct 16 ms 23848 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 12 ms 23708 KB Output is correct
12 Correct 40 ms 28740 KB Output is correct
13 Correct 59 ms 32232 KB Output is correct
14 Correct 61 ms 31432 KB Output is correct
15 Correct 77 ms 32104 KB Output is correct
16 Correct 75 ms 32192 KB Output is correct
17 Correct 63 ms 32192 KB Output is correct
18 Correct 13 ms 23752 KB Output is correct
19 Correct 57 ms 31516 KB Output is correct
20 Correct 14 ms 23776 KB Output is correct
21 Incorrect 53 ms 30756 KB Output isn't correct
22 Halted 0 ms 0 KB -