제출 #593833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593833		KrisjanisP	경주 (Race) (IOI11_race)	C++14	100 / 100	499 ms	29228 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = int;
using ii = pair<ll,ll>;

const ll MXN = 2e5;
const ll MXK = 1e6;

vector<ii> AL[MXN];
bool removed[MXN];

ll N, K;

ll subtreeSize[MXN];

// get size of a subtree
ll getSize(ll v, ll p)
{
  ll res = 1;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    res += getSize(u,v);
  }
  subtreeSize[v] = res;
  return res;
}

// find the centroid
// of a connected component
ll findCentroid(ll v, ll p, ll n)
{
  bool found = true;
  ll sum = 1;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    sum += subtreeSize[u];
    if(subtreeSize[u]>(n/2))
    {
      found = false;
      break;
    }
  }
  if((n-sum)>(n/2)) found = false;
  if(found) return v;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    ll r = findCentroid(u,v,n);
    if(r!=-1) return r;
  }
  return -1;
}

// saves the depth at which was found
// the minimum depth and the second minimum
ll found[MXK+1];

void gather(ll v, ll p, ll d, ll s)
{
  if(s>K) return;
  if(found[s]==-1) found[s] = d;
  else found[s] = min(found[s],d);
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    gather(u,v,d+1,s+w);
  }
}

ll check(ll v, ll p, ll d, ll s)
{
  if(s>K) return -1;
  ll o = K-s;
  ll res = -1;
  if(found[o]!=-1) res = found[o]+d;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    ll r = check(u,v,d+1,s+w);
    if(r!=-1)
    {
      if(res!=-1) res = min(res,r); 
      else res = r;
    }
  }
  return res;
}

void clear(ll v, ll p, ll s)
{
  if(s>K) return;
  found[s] = -1;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    clear(u,v,s+w);
  }
}

// returns -1 or minimum highways
// such that v is included in the path
ll process(ll v)
{
  ll res = -1;
  for(auto& [u,w]: AL[v])
  {
    if(removed[u]) continue;
    found[0]=0;
    ll r = check(u,v,1,w);
    if(r!=-1)
    {
      if(res!=-1) res = min(res,r); 
      else res = r;
    }
    gather(u,v,1,w);
  }

  clear(v,v,0);

  return res;
}

// returns -1 or minimum highways
// in the whole connected component
// divide and conquer
ll DACE(ll v)
{
  ll sz = getSize(v,v);
  ll c = findCentroid(v,v,sz);
  ll res = process(c);
  removed[c] = 1;
  for(auto& [u,w]: AL[c])
  {
    if(removed[u]) continue;
    ll res_u = DACE(u);
    if(res_u!=-1){
      if(res==-1) res=res_u;
      else res=min(res, res_u);
    }
  }
  return res;
}

int best_path(int n, int k, int H[][2], int L[])
{
  N = n,K = k;
  for(ll i=1;i<=K;i++) found[i]=-1;
  for(ll i=0;i<N-1;i++)
  {
    ll a=H[i][0],b=H[i][1],w=L[i];
    AL[a].emplace_back(b,w);
    AL[b].emplace_back(a,w);
  }
  return DACE(0);
}

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

race.cpp: In function 'll getSize(ll, ll)':
race.cpp:22:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'll findCentroid(ll, ll, ll)':
race.cpp:38:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp:51:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'void gather(ll, ll, ll, ll)':
race.cpp:70:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'll check(ll, ll, ll, ll)':
race.cpp:84:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'void clear(ll, ll, ll)':
race.cpp:102:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'll process(ll)':
race.cpp:115:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'll DACE(ll)':
race.cpp:142:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |   for(auto& [u,w]: AL[c])
      |             ^

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