제출 #1034472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1034472		raphaelp	경주 (Race) (IOI11_race)	C++14	9 / 100	84 ms	8924 KiB

race

#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] = 1000000;
            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);
            if (j.first - prof == K)
                best = min(best, j.second - prof2);
        }
    }
    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 = 1000000;
    dfs(0, 0, AR, dp, K, 0, 0, best);
    return ((best == 1000000) ? -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);
}*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57