oj.uz

Submission #627425

# Submission time Handle Problem Language Result Execution time Memory
627425 2022-08-12T14:52:09 Z Tien_Noob Road Closures (APIO21_roads) C++17
0 / 100
 175 ms 6492 KB 
//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.rbegin(), f.rend());
    for (int t = 0; t < 2; ++ t)
    {
        while(f.size() > max(0, k - t))
        {
            sum += f.back();
            f.pop_back();
        }
        dp[u][t] = sum;
    }
}
vector<long long>  minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
    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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 149 ms 552 KB Output is correct
3 Correct 175 ms 692 KB Output is correct
4 Correct 70 ms 572 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 63 ms 524 KB Output is correct
9 Correct 98 ms 560 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 356 KB Output is correct
12 Runtime error 16 ms 3924 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Runtime error 28 ms 6492 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 6388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 6388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 149 ms 552 KB Output is correct
3 Correct 175 ms 692 KB Output is correct
4 Correct 70 ms 572 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 63 ms 524 KB Output is correct
9 Correct 98 ms 560 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 356 KB Output is correct
12 Runtime error 16 ms 3924 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -