oj.uz

Submission #1034486

# Submission time Handle Problem Language Result Execution time Memory
1034486 2024-07-25T14:23:03 Z raphaelp Race (IOI11_race) C++14
9 / 100
 69 ms 9252 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(long long x, long long p, vector<vector<pair<long long, long long>>> &AR, map<long long, long long> &dp, long long K, long long prof, long long prof2, long long &best)
{
    map<long long, long long> M;
    M[prof] = prof2;
    for (long long i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].first == p)
            continue;
        dfs(AR[x][i].first, x, AR, dp, K, prof + AR[x][i].second, prof2 + 1, best);
        if (dp.size() > M.size())
            swap(dp, M);
        for (auto j : dp)
        {
            M[j.first] = 100000000;
            M[j.first] = min(M[j.first], j.second);
            if (M[K - j.first + 2 * prof] > 0)
                best = min(best, M[K - j.first + 2 * prof] + j.second - 2 * prof2);
            else
                M.erase(K - j.first + 2 * prof);
        }
    }
    swap(dp, M);
}
int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<long long, long long>>> AR(N);
    for (long long i = 0; i < N - 1; i++)
    {
        AR[H[i][0]].push_back({H[i][1], L[i]});
        AR[H[i][1]].push_back({H[i][0], L[i]});
    };
    map<long long, long long> dp;
    long long best = 100000000;
    dfs(0, 0, AR, dp, K, 1, 1, best);
    return ((best == 100000000) ? -1 : (int)best);
}

/*long long main()
{
    long long N, K;
    cin >> N >> K;
    long long L[N], H[N][2];
    for (long long i = 0; i < N - 1; i++)
    {
        cin >> H[i][0] >> H[i][1];
    }
    for (long long i = 0; i < N - 1; i++)
    {
        cin >> L[i];
    }
    cout << best_path(N, K, H, L);
}*/

Compilation message

race.cpp: In function 'void dfs(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::map<long long int, long long int>&, long long int, long long int, long long int, long long int&)':
race.cpp:8:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (long long i = 0; i < AR[x].size(); i++)
      |                           ~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 452 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Incorrect 1 ms 604 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 69 ms 9252 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 452 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Incorrect 1 ms 604 KB Output isn't correct
29 Halted 0 ms 0 KB -