Submission #245215

#TimeUsernameProblemLanguageResultExecution timeMemory
245215A02Race (IOI11_race)C++11
43 / 100
3091 ms190328 KiB
#include "race.h" #include <vector> #include <stdio.h> #include <stdlib.h> #include <string> #include <iostream> #include <fstream> #include <queue> using namespace std; void root_tree (vector<int> &parents, vector<vector<pair<int, int> > > &adjacent, int current){ for (int i = 0; i < adjacent[current].size(); i++){ long long child = adjacent[current][i].first; if (parents[child] == -1){ parents[child] = current; root_tree(parents, adjacent, child); } } } void process_node(int N, vector<int> &parents, vector<vector<pair<int, int> > > &adjacent, vector<vector<int> > &least_highways, int current){ least_highways[current][0] = 0; for (int i = 0; i < adjacent[current].size(); i++){ int child = adjacent[current][i].first; int d = adjacent[current][i].second; if (parents[child] == current){ if (least_highways[child][0] == N + 1){ process_node(N, parents, adjacent, least_highways, child); } for (int r = d; r < least_highways[0].size(); r++){ //cout << r << ' ' << d << ' ' << 'c' << child << ' ' << current << ' ' << least_highways[child][r - d] << endl; if (r - d >= 0){ least_highways[current][r] = min(least_highways[current][r], least_highways[child][r - d] + 1); } } } } } int best_path(int N, int K, int H[][2], int L[]) { vector<vector<pair<int, int> > > adjacent (N, vector<pair<int, int> >()); for (int i = 0; i < N - 1; i++){ adjacent[H[i][0]].push_back(make_pair(H[i][1], L[i])); adjacent[H[i][1]].push_back(make_pair(H[i][0], L[i])); } if (N <= 1000){ int best = N + 1; for (int i = 0; i < N; i++){ //cout << i << ' ' << endl; vector<pair<int, int> > distance (N, make_pair(-1, -1)); queue<int> to_visit; to_visit.push(i); distance[i].first = 0; distance[i].second = 0; while (!to_visit.empty()){ int current = to_visit.front(); to_visit.pop(); if (distance[current].second == K){ best = min(best, distance[current].first); } for (int r = 0; r < adjacent[current].size(); r++){ int next = adjacent[current][r].first; if (distance[next].first == -1){ distance[next].first = distance[current].first + 1; distance[next].second = distance[current].second + adjacent[current][r].second; to_visit.push(next); } } } } if (best == N + 1){ return -1; } return best; } else { vector<int> parents (N, -1); parents[0] = -2; root_tree(parents, adjacent, 0); vector<vector<int> > least_highways (N, vector<int> (K + 1, N + 1)); process_node(N, parents, adjacent, least_highways, 0); int best = N + 1; // for (int i = 0; i < N; i ++){ // // cout << endl; // cout << i << ":" << endl; // for (int j = 0; j <= K; j++){ // cout << least_highways[i][j] << ' '; // } // cout << endl; // // } for (int n = 0; n < N; n++){ for (int i = 0; i < adjacent[n].size(); i++){ int child1 = adjacent[n][i].first; if (parents[child1] == n){ for (int j = i + 1; j < adjacent[n].size(); j++){ int child2 = adjacent[n][j].first; if (parents[child2] == n){ int added_distance = adjacent[n][i].second + adjacent[n][j].second; for (int r = 0; r <= K - added_distance; r++){ best = min(best, 2 + least_highways[child1][r] + least_highways[child2][K - added_distance - r]); } } } } best = min (best, least_highways[n][K]); //cout << n << ' ' << best << endl; } } if (best > N){ return -1; } return best; return N; } }

Compilation message (stderr)

race.cpp: In function 'void root_tree(std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, int)':
race.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adjacent[current].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void process_node(int, std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::vector<int> >&, int)':
race.cpp:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adjacent[current].size(); i++){
                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:40:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int r = d; r < least_highways[0].size(); r++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:91:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int r = 0; r < adjacent[current].size(); r++){
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:135:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < adjacent[n].size(); i++){
                             ~~^~~~~~~~~~~~~~~~~~~~
race.cpp:138:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = i + 1; j < adjacent[n].size(); j++){
                                         ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...