제출 #777818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777818		a_aguilo	경주 (Race) (IOI11_race)	C++14	43 / 100	3067 ms	31468 KiB

race

#include "race.h"
#include<bits/stdc++.h>
 
using namespace std;
 
int n, k;
const int maxN = 200000;
const int maxK = 1000001;
vector<pair<int, int>> AdjList[maxN];
vector<int> exists;
int padre[maxN];
int subTreeSize[maxN];
int lengths[maxK];
 
void print(vector<pair<int, int>>& V){
  for(pair<int, int>& pii: V){
    cout << pii.first << " ";
  }
  cout << endl;
}
 
void preProcess(int node){
  subTreeSize[node] = 1;
  for(pair<int, int>& next: AdjList[node]){
    //cout << node << " -> " << next.first << endl;
    if(next.first != padre[node] && exists[next.first]){
      padre[next.first] = node;
      preProcess(next.first);
      subTreeSize[node] += subTreeSize[next.first];
    }
  }
  //cout << node << " " << subTreeSize[node] << endl;
}
 
int find_Centroid(int node, int sze){
  for(int i = 0; i < AdjList[node].size(); ++i){
    pair<int, int> next = AdjList[node][i];
    if(next.first == padre[node] || !exists[next.first]) continue;
    if(subTreeSize[next.first] > (sze/2)) {
      i = -1;
      node = next.first;
    }
  }
  return node;
}
 
void findDistances(int node, int currDist, int numEdges, vector<pair<int, int>>& V){
  if(currDist > k) return;
  V.push_back({currDist, numEdges});
  for(pair<int, int>& next: AdjList[node]){
    if(exists[next.first] && next.first != padre[node]){
      padre[next.first] = node;
      findDistances(next.first, currDist+next.second, numEdges+1, V);
    }
  }
}
 
int solveSubTree(int node){
  padre[node] = node;
  preProcess(node);
  int sze = subTreeSize[node];
  node = find_Centroid(node, sze);
  //cout << node << endl;
  padre[node] = node;
 
  fill(lengths, lengths + k + 1, 1e9);
  int ans = 1e9;
 
  for(pair<int, int>& next: AdjList[node]){
    if(next.first == padre[node]) continue;
    if(!exists[next.first]) continue;
    padre[next.first] = node;
    vector<pair<int, int>> prov;
    findDistances(next.first, next.second, 1, prov);
    for(pair<int, int>& val: prov){
      int d = val.first;
      int edges = val.second;
      ans = min(ans, lengths[k - d] + edges);
    }
    for(pair<int, int>& val: prov){
      int d = val.first;
      int edges = val.second;
      lengths[d] = min(lengths[d], edges);
    }
    /*
    cout << node << " -> " << next.first << endl;
    for(int i = 1; i <= k; ++i) cout << lengths[i] << " ";
    cout << endl;*/
  }
  ans = min(ans, lengths[k]);
 
  exists[node] = 0;
 
  for(pair<int, int>& next: AdjList[node]){
    if(exists[next.first]) ans = min(ans, solveSubTree(next.first));
  }
  return ans;
}
 
int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  exists = vector<int>(N, 1);
  int a, b, c;
  for(int i = 0; i < N-1; ++i){
    a = H[i][0];
    b = H[i][1];
    c = L[i];
    AdjList[a].push_back({b, c});
    AdjList[b].push_back({a, c});
  }
  /*
  for(int i = 0; i < N-1; ++i){
    cout << i << '\t';
    print(AdjList[i]);
  }*/
  int res = solveSubTree(0);
  if(res == 1e9) return -1;
  return res;
}
 
/*
int main(){
  int N, K;
  cin >> N >> K;
  int H[N-1][2];
  int L[N-1];
  for(int i = 0; i < N-1; ++i) cin >> H[i][0] >> H[i][1] >> L[i];
  cout << best_path(N, K, H, L);
  return 0;
}*/

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

race.cpp: In function 'int find_Centroid(int, int)':
race.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i = 0; i < AdjList[node].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~

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