제출 #720747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720747		kunzaZa183	경주 (Race) (IOI11_race)	C++17	21 / 100	3055 ms	22932 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct kun
{
  pair<int, int> higher, lower; // depth subtree
  kun()
  {
    higher = {1000000000000000, 1000000000000000}, lower = {1000000000000000, 1000000000000000};
  }
};
int dfs(int cur, int par, vector<vector<pair<int, int>>> &adjlist, vector<bool> &node, vector<int> &siz)
{
  siz[cur] = 1;
  for (auto a : adjlist[cur])
    if (a.first != par && node[a.first])
      siz[cur] += dfs(a.first, cur, adjlist, node, siz);
  return siz[cur];
}
int findcen(int cur, int par, vector<vector<pair<int, int>>> &adjlist, vector<bool> &node, vector<int> &siz, int n)
{
  int maxi = LLONG_MIN, maxid;
  for (auto a : adjlist[cur])
    if (a.first != par && node[a.first])
      if (siz[a.first] > maxi)
      {
        maxi = siz[a.first];
        maxid = a.first;
      }
  if (maxi <= n / 2)
    return cur;
  return findcen(maxid, cur, adjlist, node, siz, n);
}
int dfscen(int cur, int par, int dist, int depth, int head, map<int, kun> &mii, vector<vector<pair<int, int>>> &adjlist, vector<bool> &node, vector<int> &siz)
{
  siz[cur] = 1;
  if (depth < mii[dist].higher.first)
  {
    swap(mii[dist].higher, mii[dist].lower);
    mii[dist].higher = {depth, head};
  }
  else if (depth < mii[dist].lower.first)
    mii[dist].lower = {depth, head};
  for (auto a : adjlist[cur])
    if (a.first != par && node[a.first])
      siz[cur] += dfscen(a.first, cur, dist + a.second, depth + 1, head, mii, adjlist, node, siz);
  return siz[cur];
}
int anssubtree(int root, vector<vector<pair<int, int>>> &adjlist, vector<bool> &node, int n, int k)
{
  vector<int> siz(adjlist.size());
  dfs(root, root, adjlist, node, siz);
  int centroid = findcen(root, root, adjlist, node, siz, n);
  map<int, kun> mii; /*length vector<depth, subtree>*/
  for (auto a : adjlist[centroid])
    if (node[a.first])
      dfscen(a.first, centroid, a.second, 1, a.first, mii, adjlist, node, siz);
  mii[0].lower = {0, 0}, mii[0].higher = {0, 0};
  int shortest = 1000000000000000;
  for (auto &a : mii)
    if (a.first <= k / 2)
    {
      kun tmp = mii[k - a.first];
      if (a.second.higher.second != tmp.higher.second)
        shortest = min(shortest, a.second.higher.first + tmp.higher.first);
      if (a.second.lower.second != tmp.higher.second)
        shortest = min(shortest, a.second.lower.first + tmp.higher.first);
      if (a.second.higher.second != tmp.lower.second)
        shortest = min(shortest, a.second.higher.first + tmp.lower.first);
      if (a.second.lower.second != tmp.lower.second)
        shortest = min(shortest, a.second.lower.first + tmp.lower.first);
    }
  node[centroid] = 0;
  for (auto a : adjlist[centroid])
    if (node[a.first])
      shortest = min(shortest, anssubtree(a.first, adjlist, node, siz[a.first], k));
  return shortest;
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
  vector<vector<pair<int, int>>> adjlist(N);
  for (int i = 0; i < N - 1; i++)
    adjlist[H[i][0]].push_back({H[i][1], L[i]}), adjlist[H[i][1]].push_back({H[i][0], L[i]});
  vector<bool> vb(N, 1);
  int x = anssubtree(0, adjlist, vb, N, K);
  if (x == 1000000000000000)
    x = -1;
  return x;
}

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

race.cpp: In function 'long long int findcen(long long int, long long int, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<bool>&, std::vector<long long int>&, long long int)':
race.cpp:22:25: warning: 'maxid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   int maxi = LLONG_MIN, maxid;
      |                         ^~~~~

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