제출 #877861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877861		Matjaz	경주 (Race) (IOI11_race)	C++14	31 / 100	2049 ms	262144 KiB

race

#include "race.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

struct edge{
    int u;
    int l;
};

int N,K;
vector<vector<edge> > s;

int best;


vector<int> paths(int x, int p){
    
    vector<int> possible(K+1, N);
    possible[0] = 0;
    
    for (int i=0;i<s[x].size();i++){
        if (s[x][i].u == p) continue;
        vector<int> pths = paths(s[x][i].u, x);
        for (int j=0;j<=K;j++){
            if (pths[j] == N) continue;
            if (j + s[x][i].l > K) continue;
            if (possible[K - j - s[x][i].l] != N){
                best = min(best, possible[K - j - s[x][i].l] + 1 + pths[j]);
            }
        }
        
        for (int j=0;j<=K;j++){
            if (pths[j] == N) continue;
            if (j + s[x][i].l > K) continue;
            possible[j + s[x][i].l] = min(possible[j + s[x][i].l], 1 + pths[j]);
        }
    }
    
    /*cout << x << ": ";
    for (int i=0;i<K+1;i++) cout << possible[i] << " ";
    cout << endl;*/
    
    return possible;
}



int best_path(int _N, int _K, int H[][2], int L[]){
    N = _N; K = _K;
    s.assign(N, vector<edge> ());
    for (int i=0;i<N-1;i++){
        edge e,f;
        e.l = L[i];
        e.u = H[i][0];
        f.l = L[i];
        f.u = H[i][1];
        s[H[i][1]].push_back(e);
        s[H[i][0]].push_back(f);
    }
    
    best = N;
    
    paths(0, -1);
    
    if (best == N) return -1; else return best;
}

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

race.cpp: In function 'std::vector<int> paths(int, int)':
race.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57