Submission #877875

#	Time	Username	Problem	Language	Result	Execution time	Memory
877875		Matjaz	Race (IOI11_race)	C++14	31 / 100	193 ms	118492 KiB

race

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

struct edge{
    int u;
    int l;
};

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

int best;


vector<int> pathssmallK(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 = pathssmallK(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;
}

map<int,int> paths(int x, int p){
    
    map<int,int> possible;
    possible[0] = 0;
    
    for (int i=0;i<s[x].size();i++){
        if (s[x][i].u == p) continue;
        map<int, int> pths = paths(s[x][i].u, x);
        int l = s[x][i].l;
        
        for (map<int,int>::iterator it = pths.begin(); it != pths.end(); it++){
            if (possible.count(K - l - it -> first) > 0){
                best = min(best, 1 + it -> second + possible[K - l - it -> first]);
                
            }
        }
        
        for (map<int,int>::iterator it = pths.begin(); it != pths.end(); it++){
            if (l + it -> second > K) continue;
            if (possible.count(l + it -> second) > 0)
                possible[l + it -> second] = min(possible[l + it -> second], 1 + it -> second); else possible[l + it -> second] = 1 + it -> second;
        }
    }
    
   /* cout << x << ": " << endl;
    for (map<int,int>::iterator it = possible.begin(); it != possible.end(); it++) cout << it -> first << " " << it -> second << endl;
    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;
    if (K <= 100) pathssmallK(0, -1); else
    paths(0, -1);
    
    if (best == N) return -1; else return best;
}

Compilation message (stderr)

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