제출 #480507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480507		AURRUM	경주 (Race) (IOI11_race)	C++17	100 / 100	1198 ms	47264 KiB

race

#include "race.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <queue>
#include <time.h>
#include <bitset>
#include <unordered_map>
 
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define ft first
#define sc second
#define add push_back
#define all(v) v.begin(),v.end()
#define mpr make_pair
#define sz(v) (ll)v.size()
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define FORD(i,a,b) for(ll i = (a); i >= (b); i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
const ll MOD = 1e9+7;
const ll INF = 1e9;
const int N = 200005;

vector<pll> g[N];
ll answ = -1;
ll entsize[N];
bool used[N];
ll nn = 0;
ll k;

void dfs_sz(int u, int p)
{
  nn++;
  entsize[u] = 1;
  for(auto f : g[u])
  {
    if(f.ft == p or used[f.ft])
    {
      continue;
    }
    dfs_sz(f.ft,u);
    entsize[u]+=entsize[f.ft];
  }
}

int find_center(int u, int p)
{
  int mx_size = -1;
  int vert = -1;
  for(auto f : g[u])
  {
    if(f.ft == p or used[f.ft])
    {
      continue;
    }
    if(entsize[f.ft] > mx_size)
    {
      mx_size = entsize[f.ft];
      vert = f.ft;
    }
  }
  if(2*mx_size <= nn)
  {
    return u;
  }
  return find_center(vert,u);
}

int find_centroid(int u)
{
  nn = 0;
  dfs_sz(u,u);
  int center = find_center(u,u);
  //dfs_sz(center,center);
  return center;
}

vector<pll> mas;
map<ll,ll> mp;

void update(ll o)
{
  if(answ == -1 or o < answ)
  {
    answ = o;
  }
}

void solve(int u, int p, int dist, int depth)
{
  if(p != u)
  {
    mas.add(mpr(dist,depth));
  }
  for(auto f : g[u])
  {
    if(f.ft == p or used[f.ft])
    {
      continue;
    }
    solve(f.ft,u,dist+f.sc,depth+1);
    if(p == u)
    {
      for(auto hg : mas)
      {
        if(hg.ft > k)
        {
          continue;
        }
        else if(hg.ft == k)
        {
          update(hg.sc);
        }
        else
        {
          if(mp.find(k-hg.ft) != mp.end())
          {
            update(mp[k-hg.ft] + hg.sc);
          }
        }
      }
      for(auto hg : mas)
      {
        if(hg.ft > k)
        {
          continue;
        }
        if(mp.find(hg.ft) == mp.end())
        {
          mp[hg.ft] = hg.sc;
        }
        else
        {
          mp[hg.ft] = min(mp[hg.ft], hg.sc);
        }
      }
      mas.clear();
    }
  }
}

void centroid_decomposition()
{
  queue<ll> q;
  q.push(1);

  while(!q.empty())
  {
    int vnow = q.front();
    q.pop();

    mp.clear();

    int cen = find_centroid(vnow);
    solve(cen,cen,0,0);
    used[cen] = 1;
    for(auto f : g[cen])
    {
      if(used[f.ft] or entsize[f.ft] == 1)
      {
        continue;
      }
      q.push(f.ft);
    }
  }
}

int best_path(int n, int K, int H[][2], int L[])
{

  k = K;
  FOR(i,0,n-1)
  {
    g[H[i][0]].add(mpr(H[i][1],L[i]));
    g[H[i][1]].add(mpr(H[i][0],L[i]));
  }

  centroid_decomposition();

  return answ;
}

// int main()
// {

//   int l[] = {3,4,5,4,6,3,2,5,6,7};
//   int h[][2] = {{0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10}};
//   cout<<best_path(11,12,h,l)<<endl;

//   //int l[] = {1,1};
//   //int h[][2] = {{0,1},{1,2}};
//   //cout<<best_path(3,3,h,l)<<endl;
  

//   return 0;
// }

/* 
 
░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░
▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒
▓▓▓▒░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▒░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▒░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▒▒░░░░░░▒▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▒░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▒░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▒░▒▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓▒░░▒▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓▓▓▓▓▓
▓▓▓▓▓▓▒░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░▒▓▓▓▓▓
▓▓▓▓▓▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░░▒▓▓▓
▓▓▓▓▒░░░░░░░░░░░▒▓▓▓▓▓▓▓▓▓▒░░░░░░░░░░░░▒▓▓
▓▓▓▓▓▒░░░░░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░░░░░▒▓▓▓
▓▓▓▓▓▓▒░░░░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒░░░░░▒▓▓▓▓
▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒
░▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒░
⠀⠀⠀⠀⠀
*/

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