제출 #593736

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

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll,ll>;

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

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

ll N, K;

// find the centroid
// of a connected component
ll findCentroid(ll v)
{
  return v;
}

// 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;
  if(found[o]!=-1) return found[o]+d;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    return check(u,v,d+1,s+w);
  }
  return -1;
}

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)
{
  vector<ll> vec;

  ll res = -1;
  for(auto& [u,w]: AL[v])
  {
    if(removed[u]) continue;
    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);
  }
  if(found[K]!=-1)
  {
      if(res!=-1) res = min(res,found[K]); 
      else res = found[K];
  }
  for(auto& [u,w]: AL[v]) clear(u,v,w);

  return res;
}

// returns -1 or minimum highways
// in the whole connected component
// divide and conquer
ll DACE(ll v)
{
  ll c = findCentroid(v);
  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)
      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 'void gather(ll, ll, ll, ll)':
race.cpp:31:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'll check(ll, ll, ll, ll)':
race.cpp:44:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'void clear(ll, ll, ll)':
race.cpp:57:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp: In function 'll process(ll)':
race.cpp:72:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   for(auto& [u,w]: AL[v])
      |             ^
race.cpp:88:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |   for(auto& [u,w]: AL[v]) clear(u,v,w);
      |             ^
race.cpp: In function 'll DACE(ll)':
race.cpp:101:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |   for(auto& [u,w]: AL[c])
      |             ^

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